给一些数， 有几个操作，求区间内数的和，修改区间内某个位置的值，---- > 区间求（修改）和。
线段树：
#include <cstdio> #include <cstring> #include <iostream> #define max(a, b) a>b?a:b const int MAXN = 50050; using namespace std; struct Node { int left, right, sum; } tree[MAXN*3]; int n, num[MAXN]; void Build(int root, int left, int right) { tree[root].left = left; tree[root].right = right; if(left == right) { tree[root].sum = num[left]; return; } int mid = (left+right)>>1; Build(root<<1, left, mid); Build(root<<1|1, mid+1, right); // tree[root].sum = tree[root<<1].sum + tree[root<<1|1].sum; } void Update(int root, int pos, int val) { if(tree[root].left == tree[root].right) { tree[root].sum += val; return; } int mid = (tree[root].left + tree[root].right) >> 1; if(pos <= mid) Update(root<<1, pos, val); else Update(root<<1|1, pos, val); tree[root].sum = tree[root<<1].sum + tree[root<<1|1].sum; } int Query(int root, int left, int right) { if(left == tree[root].left && right == tree[root].right) return tree[root].sum; int mid = (tree[root].left + tree[root].right) >> 1; if(right <= mid) return Query(root<<1, left, right); else if(left > mid) return Query(root<<1|1, left, right); else return Query(root<<1, left, mid) + Query(root<<1|1, mid+1, right); } int main() { int t, temp = 1; scanf("%d", &t); while(t--) { scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &num[i]); Build(1, 1, n); printf("Case %d: ", temp++); char str[20]; int a, b; while(~scanf("%s", str)) { if(str[0] == 'E') break; scanf("%d %d", &a, &b); if(str[0] == 'Q') printf("%d ", Query(1, a, b)); if(str[0] == 'S') Update(1, a, -b); if(str[0] == 'A') Update(1, a, b); } } return 0; }
树状数组：
函数Odd()求的是： 为pos在二进制下末尾0的个数;
http://blog.csdn.net/cambridgeacm/article/details/7771782# #include <cstdio> #include <cstring> #include <iostream> using namespace std; int n, a[50005]; int Odd(int src) { return src & (src^(src-1)); } void Update(int pos, int val) { while(pos <= n) { a[pos] += val; pos += Odd(pos); } } int Getsum(int pos) { int sum = 0; while(pos > 0) { sum += a[pos]; pos -= Odd(pos); } return sum; } int main() { int t; scanf("%d", &t); for(int Q = 1; Q <= t; Q++) { memset(a, 0, sizeof(a)); scanf("%d", &n); for(int i = 1; i <= n; i++) { int num; scanf("%d", &num); Update(i, num); } printf("Case %d: ", Q); char str[10]; while(scanf("%s", str), str[0] != 'E') { int a, b; scanf("%d %d", &a, &b); if(str[0] == 'A') Update(a, b); else if(str[0] == 'S') Update(a, -b); else //if(str[0] == 'Q'); printf("%d ", Getsum(b) - Getsum(a-1)); } } return 0; }
New code:
#include <cstdio> #include <cstring> #define N 50001 int n, num[N]; struct Node{ int sum, left, right; }tree[N*3]; int Build(int root, int left, int right){ tree[root].left = left; tree[root].right = right; if(left == right) return tree[root].sum = num[left]; int mid = (left+right) / 2; Build(root<<1, left, mid); Build(root<<1|1, mid+1, right); tree[root].sum = tree[root<<1].sum + tree[root<<1|1].sum; } int Update(int root, int pos, int val){ if(tree[root].left == tree[root].right) return tree[root].sum += val; int mid = (tree[root].left+tree[root].right) / 2; if(pos <= mid) Update(root<<1, pos, val); else Update(root<<1|1, pos, val); tree[root].sum = tree[root<<1].sum + tree[root<<1|1].sum; } int Query(int root, int left, int right){ if(left == tree[root].left && right == tree[root].right) return tree[root].sum; int mid = (tree[root].left + tree[root].right) / 2; if(right <= mid) return Query(root<<1, left, right); else if(left > mid) return Query(root<<1|1, left, right); else return Query(root<<1, left, mid) + Query(root<<1|1, mid+1, right); } int main(){ int t, tem = 1; scanf("%d", &t); while(t--){ scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &num[i]); Build(1, 1, n); printf("Case %d: ", tem++); char str[10]; while(scanf("%s", str) != EOF){ if(str[0] == 'E') break; int a, b; scanf("%d%d", &a, &b); if(str[0] == 'Q') printf("%d ", Query(1, a, b)); if(str[0] == 'A') Update(1, a, b); if(str[0] == 'S') Update(1, a, -b); } } return 0; }