codeforces果然名不虚传，仔细研读了该篇文章后感觉受益良多！
其实这篇文章探讨的就是zkw,其中的一些写法让我大开眼界，感觉是zkw那篇论文的又一个提升：
- 内存不再是2的幂了，直接就是\(2n\)，zkw应该万万没想到吧。
- zkw的PowerPoint下标的处理有点麻烦，左边又要减一，事实上不用这么麻烦。
这里贴两个模板：
单点加，区间求和
题目。
#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 50000;
int n;
struct SegmentTree {
int T[MAXN * 2];
void init() {
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", T + n + i);
for (int i = n - 1; i; i--)
T[i] = T[i << 1] + T[i << 1 ^ 1];
}
void modify(int i, int d) {
i += n - 1;
for (; i; i >>= 1) T[i] += d;
}
int query(int l, int r) {
l += n - 1;
r += n;
int ret = 0;
for (; l < r; l >>= 1, r >>= 1) {
if (l & 1) ret += T[l ++];
if (r & 1) ret += T[-- r];
}
return ret;
}
};
SegmentTree T;
int main() {
int cases;
scanf("%d", &cases);
for (int i = 0; i < cases; i++) {
printf("Case %d:\n", i + 1);
T.init();
while (true) {
char s[16];
int a, b;
scanf("%s", s);
if (s[0] == 'E') break;
scanf("%d%d", &a, &b);
if (s[0] == 'Q') {
printf("%d\n", T.query(a, b));
}
else {
if (s[0] == 'S') b = - b;
T.modify(a, b);
}
}
}
return 0;
}
区间加，区间求和
题目。
这个是我以前一直没弄懂的，现在豁然开朗。
#include <cstdio>
const int MAXN = (int) 1e5;
int n, m, h;
long long t[MAXN * 2];
int d[MAXN];
void apply(int p, int value, int k) {
t[p] += (long long) value * k;
if (p < n) d[p] += value;
}
void push(int p) {
for (int s = h - 1, k = 1 << (h - 1); s; s--, k >>= 1) {
int i = p >> s;
if (d[i]) {
apply(i << 1, d[i], k >> 1);
apply(i << 1 | 1, d[i], k >> 1);
d[i] = 0;
}
}
}
void build(int p) {
p >>= 1;
for (int k = 2; p; p >>= 1, k <<= 1) {
t[p] = t[p << 1] + t[p << 1 | 1] + (long long) d[p] * k;
}
}
void modify(int l, int r, int value) {
l += n, r += n;
push(l);
push(r - 1);
int l0 = l, r0 = r;
for (int k = 1; l < r; l >>= 1, r >>= 1, k <<= 1) {
if (l & 1) apply(l++, value, k);
if (r & 1) apply(--r, value, k);
}
build(l0);
build(r0 - 1);
}
long long query(int l, int r) {
l += n, r += n;
long long res = 0;
push(l);
push(r - 1);
for (; l < r; l >>= 1, r >>= 1) {
if (l & 1) res += t[l++];
if (r & 1) res += t[--r];
}
return res;
}
int main() {
scanf("%d%d", &n, &m);
while (1 << h <= n) h++;
for (int i = 0; i < n; i++)
scanf("%lld", t + n + i);
for (int i = n - 1; i; i--)
t[i] = t[i << 1] + t[i << 1 | 1];
for (int i = 0; i < m; i++) {
char command;
scanf("\n%c", &command);
if (command == 'C') {
int l, r, value;
scanf("%d%d%d", &l, &r, &value);
l--;
modify(l, r, value);
}
else {
int l, r;
scanf("%d%d", &l, &r);
l--;
printf("%lld\n", query(l, r));
}
}
return 0;
}