一个区间，两种操作：区间求和，单点修改。
#include#include #include #include using namespace std;#define maxn 100000 + 1000int n, a[maxn], C[maxn];int lowbit(int x){ return x & -x;}void add(int x, int val){ for (int i = x; i <= n; i += lowbit(i)) C[i] += val;}int sum(int x){ int ans = 0; for (int i = x; i > 0; i -= lowbit(i)) ans += C[i]; return ans;}int main(){ int t; scanf("%d", &t); for (int ca = 1; ca <= t; ca++) { scanf("%d", &n); memset(C, 0, sizeof(C)); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); add(i, a[i]); } printf("Case %d:\n", ca); char s[10]; while(~scanf("%s", s) && s[0] != 'E') { int l, r; scanf("%d%d", &l, &r); if (s[0] == 'A') add(l, r); if (s[0] == 'S') add(l, -r); if (s[0] == 'Q') printf("%d\n", sum(r) - sum(l-1)); } }}
单点修改，区间求最大值。
#include#include #include #include using namespace std;#define maxn 200000 + 1000int n, m, a[maxn], C[maxn];int lowbit(int x){ return x & -x;}void updata(int x, int val){ a[x] = val; for (int i = x; i <= n; i += lowbit(i)) C[i] = max(C[i], val);} int found(int l, int r){ int ans = a[r]; while(l != r) { for (r -= 1; r - lowbit(r) >= l; r -= lowbit(r)) ans = max(ans, C[r]); ans = max(ans, a[r]); } return ans;}int main(){ while(~scanf("%d%d", &n, &m)) { memset(C, 0, sizeof(C)); memset(a, 0, sizeof(a)); for (int i = 1; i <= n; i++) { int x; scanf("%d", &a[i]); updata(i, a[i]); } char c; for (int i = 1; i <= m; i++) { getchar(); int l, r; scanf("%c%d%d", &c, &l, &r); if (c == 'U') updata(l, r); if (c == 'Q') printf("%d\n", found(l, r)); } }}