POJ3468 线段树的区间操作

今晚做这题，因为使用 int 型贡献了不少的 WA，最后改成 long long 就过了。这题一看就可以明显注意到使用线段树来写了，原来不是很经常写更新区间的问题，在此对更新区间查找区间的题目进行一下总结。

更新区间的函数，注意记录一个增量 $add$ 来表示这个区间从它的父亲结点继承下来的增量，当我们找到一个区间时候，就把增量全部转化为 $sum$，也就是这个区间的总和，然后对 $add$ 进行继承操作，最后清空 $add$，之后就是三种情况的二分了。

对于求和函数，类似的，我们要先处理继承问题，然后二分查找结果，最后返回。

更新区间查找区间的题目一般比较烦，需要记录父亲结点继承的增量，所以我们把 $seg[k]$ 对应的区间的边界也加入到结点信息中，这样可以大大减少函数的参数。

我的代码如下：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;

typedef long long LL;
const int MAX = 100100;
struct Node {
  int low, high;
  LL sum;
  LL add;
} seg[4 * MAX];
int a[MAX];

void init(int k, int low, int high);
void update(int k, int a, int b, int v);
LL sum(int k, int a, int b);

int main() {
  int n, q;
  char op[2];
  int x, y, v;
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  init(1, 1, n);
  for (int i = 0; i < q; i++) {
    scanf("%s", op);
    if (op[0] == 'Q') {
      scanf("%d%d", &x, &y);
      printf("%lld\n", sum(1, x, y));
    } else if (op[0] == 'C') {
      scanf("%d%d%d", &x, &y, &v);
      update(1, x, y, v);
    }
  }
  return 0;
}

void init(int k, int low, int high) {
  seg[k].add = 0;
  seg[k].low = low;
  seg[k].high = high;
  if (low == high) {
    seg[k].sum = a[low];
    return;
  }
  int mid = (low + high) >> 1;
  init(2 * k, low, mid);
  init(2 * k + 1, mid + 1, high);
  seg[k].sum = seg[2 * k].sum + seg[2 * k + 1].sum;
}

void update(int k, int a, int b, int v) {
  seg[k].sum += (seg[k].high - seg[k].low + 1) * seg[k].add;
  if (seg[k].low != seg[k].high) {
    seg[2 * k].add += seg[k].add;
    seg[2 * k + 1].add += seg[k].add;
  }
  seg[k].add = 0;
  if (a > seg[k].high || b < seg[k].low) return;
  if (a <= seg[k].low && b >= seg[k].high) {
    seg[k].sum += (seg[k].high - seg[k].low + 1) * v;
    if (seg[k].low != seg[k].high) {
      seg[2 * k].add += v;
      seg[2 * k + 1].add += v;
    }
    return;
  }
  update(2 * k, a, b, v);
  update(2 * k + 1, a, b, v);
  seg[k].sum = seg[2 * k].sum + seg[2 * k + 1].sum;
}

LL sum(int k, int a, int b) {
  seg[k].sum += (seg[k].high - seg[k].low + 1) * seg[k].add;
  if (seg[k].low != seg[k].high) {
    seg[2 * k].add += seg[k].add;
    seg[2 * k + 1].add += seg[k].add;
  }
  seg[k].add = 0;
  if (a > seg[k].high || b < seg[k].low) return 0;
  if (a <= seg[k].low && b >= seg[k].high) return seg[k].sum;
  LL k1 = sum(2 * k, a, b);
  LL k2 = sum(2 * k + 1, a, b);
  return k1 + k2;
}