对于单点更新，区间查询，更喜欢用树状数组解。
hdu1166 敌兵布阵
BIT二叉索引树，树状数组版
//代码贴上去时，有时前后会有一个html标签，删了
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <cstring> #define N 50007 inline int lowbit(int x) { return x & (-x); } int bit[N], n, a[N]; void add(int pos, int val) { while (pos <= n) { bit[pos] += val; pos += lowbit(pos); } } int sum(int pos) { int res = 0; while (pos > 0) { res += bit[pos]; pos -= lowbit(pos); } return res; } int main() { int T, kase = 0; scanf("%d", &T); while (T--) { printf("Case %d:\n", ++kase); memset(bit, 0, sizeof bit); memset(a, 0, sizeof a); scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", a + i); add(i, a[i]); } char opt[10]; int x, y; while (~scanf("%s", opt)) { if (!strcmp(opt, "End")) break; scanf("%d%d", &x, &y); if (opt[0] == 'A') { add(x, y); } else if (opt[0] == 'S') { add(x, -1 * y); } else if (opt[0] == 'Q') { printf("%d\n", sum(y) - sum(x - 1)); } } } return 0; }
线段树版
//线段树单点更新，区间查询。本题线段树srcTree存区间和 #include <cstdio> #include <cstring> #define N 50007 int n, secTree[N << 2]; void build(int rt, int l, int r) { if (l == r) { scanf("%d", secTree + rt); return; } int mid = l + r >> 1; build(rt << 1, l, mid); build(rt << 1 | 1, mid + 1, r); secTree[rt] = secTree[rt << 1] + secTree[rt << 1 | 1]; } void update(int rt, int l, int r, int pos, int inc) { //根root, root所在区间[left, right]， pos位置增加inc if (l == r) { secTree[rt] += inc; //也可以用一个数组存ary[N]，为了省空间,secTree = ary[cur++] return; } int mid = l + r >> 1; if (pos <= mid) update(rt << 1, l, mid, pos, inc); else update(rt << 1 | 1, mid + 1, r, pos, inc); secTree[rt] = secTree[rt << 1] + secTree[rt << 1 | 1]; } int query(int rt, int l, int r, int L, int R) { //在（left, right)中查询 L , R (L, R)待查询区间 if (L <= l && r <= R) { return secTree[rt]; } int mid = l + r >> 1; int ans = 0; if (L <= mid) ans += query(rt << 1, l, mid, L, R); if (R > mid) ans += query(rt << 1 | 1, mid + 1, r, L, R); return ans; } int main() { int T, kase = 0; scanf("%d", &T); while(T-- > 0) { memset(secTree, 0, sizeof secTree); printf("Case %d:\n", ++kase); scanf("%d", &n); build(1, 1, n); char cmd[10]; while(~scanf("%s", cmd) && strcmp(cmd, "End")) { int a, b; scanf("%d%d", &a, &b); if (!strcmp(cmd, "Query")) { printf("%d\n", query(1, 1, n, a, b)); } else if (!strcmp(cmd, "Add")) { update(1, 1, n, a, b); } else if (!strcmp(cmd, "Sub")) { update(1, 1, n, a, -b); } } } return 0; }
附： 树状数组还可用于二维的面修改查询操作
poj1195
#define _CRT_SECURE_NO_WARNINGS #include <cstring> #include <iostream> #include <cstdio> #include <cstring> using namespace std; #define MAX 1100 int C[MAX][MAX]; inline int lowbit(int x) { return (x & (-x)); } int s; void add(int y, int x, int val) { for (int i = y; i <= s; i += lowbit(i)) for (int j = x; j <= s; j += lowbit(j)) C[i][j] += val; } int sum(int y, int x) { //二维线段树小心宽和高可能不一样，不一定是n，我刚在poj2029栽了个跟头 //询问矩阵(1,1):(y,x)中元素的和 int res = 0; for (int i = y; i > 0; i -= lowbit(i)) for (int j = x; j > 0; j -= lowbit(j)) res += C[i][j]; return res; } int main() { int cmd, y, x, val; while (~scanf("%d", &cmd) && cmd != 3) { switch (cmd) { case 0: scanf("%d", &s); memset(C, 0, sizeof C); break; case 1: scanf("%d%d%d", &x, &y, &val); add(y + 1, x + 1, val); break; case 2: int l, b, r, t; scanf("%d%d%d%d", &l, &b, &r, &t); l++, b++, r++, t++; printf("%d\n", sum(t, r) - sum(b - 1, r) - sum(t, l - 1) + sum(b - 1, l - 1)); break; } } return 0; } 一天最多贴5篇
