敌兵布阵php
仍然是敌兵布阵那题,题目大意:给你一串数,而后会根据题意选择一点增长或减小,或者询问某区间的人数有多少?以前用线段树写了,而这题能够用树状树状来作,更加方便更加快速。ios
说下树状数组的三个主要函数:(神同样的函数,不仅这些用处!!!)数组
1.lowbit(int i)函数
2.update(int i, int x)spa
3.sum(int i)code
#include <iostream> #include <stdio.h> #include <memory.h> using namespace std; int n, a[50005]; char sh[15]; int lowbit(int i) //树状数组最巧妙之处:i&(-i) { return i&(-i); } void update(int i, int val) //更新函数 { while(i <= n) { a[i] += val; i += lowbit(i); } } int sum(int i) //求和函数 { int sum = 0; while(i > 0) { sum += a[i]; i -= lowbit(i); } return sum; } int main() { int i, val, t, x, y, zz = 1; scanf("%d", &t); while(t--) { memset(a, 0, sizeof(a)); scanf("%d", &n); for(i = 1; i <= n; i++) { scanf("%d", &val); update(i, val); } printf("Case %d:\n", zz++); while(scanf("%s", sh)) { if(sh[0] == 'E') break; scanf("%d %d", &x, &y); if(sh[0] == 'A') update(x, y); else if(sh[0] == 'S') update(x, -y); else printf("%d\n", sum(y)-sum(x-1)); //两段区间和相减 } } return 0; }