codeforces果然名不虚传，仔细研读了该篇后感觉受益良多！

其实这篇文章探讨的就是zkw,其中的一些写法让我大开眼界，感觉是zkw那篇论文的又一个提升：

• 内存不再是2的幂了，直接就是\(2n\)，zkw应该万万没想到吧。
• zkw的PowerPoint下标的处理有点麻烦，左边又要减一，事实上不用这么麻烦。

这里贴两个模板：

单点加，区间求和

。

#include 
    
     #include 
     
      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 
    
     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;}