线段树

线段树的原理：把[1…n]分解为若干子区间（数量上不超过4*n），将每个子区间[L,R]都分解。这里必须要符合区间加法。
符合区间加法的例子：
数字之和——总数字之和 = 左区间数字之和 + 右区间数字之和
最大公因数(GCD)——总GCD = gcd( 左区间GCD , 右区间GCD );
最大值——总最大值=max(左区间最大值，右区间最大值)

如果用正常的数组，单点修改O(1)，区间查询O(n)；使用前缀和算法，单点修改O(n)，区间查询O(1)，当两种操作数量都很大时，整体复杂度近似可以看做O(n)。而从上面的图中，可以看出的是，线段树可以把单点修改和区间查询都降到O(logn)，这样整体复杂度就还是O(logn)。原因就在于满二叉树最多只需要修改层高个数的节点，严谨证明可以参见这篇博客 。区间修改需要用到lazy标记。

洛谷 P3372 【模板】线段树 1 满分代码

// https://www.luogu.com.cn/problem/P3372
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x7fffffff;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;

struct sgt {
  int l, r;
  ll dat, lz;
} t[N * 4];
// lz标记的含义：本区间已经被更新过了，但是子区间却没有被更新过，被更新的信息是什么
// （区间求和只用记录有没有被访问过，而区间加减乘除等多种操作的问题则要记录进行的是哪一种操作）
// 相对标记和绝对标记
int a[N];  // 原始数组
void build(int p, int l, int r) {
  t[p].l = l, t[p].r = r;
  if (l == r) {
    t[p].dat = a[l];
    return;
  }
  int mid = (l + r) / 2;
  build(p * 2, l, mid);
  build(p * 2 + 1, mid + 1, r);
  t[p].dat = t[p * 2].dat + t[p * 2 + 1].dat;
}

// 单点修改:把A[x]的值设为v
void change(int p, int x, int v) {
  if (t[p].l == t[p].r) {
    t[p].dat = v;
    return;
  }  //找到叶节点
  int mid = (t[p].l + t[p].r) / 2;
  if (x <= mid)  //左子树
    change(p * 2, x, v);
  else  // 右子树
    change(p * 2 + 1, x, v);
  t[p].dat = t[p * 2].dat + t[p * 2 + 1].dat;
}

// 下放lz标记
void pushdown(int p) {
  if (t[p].lz) {
    t[p * 2].dat += t[p].lz * (t[p * 2].r - t[p * 2].l + 1);  // 更新左儿子
    t[p * 2 + 1].dat +=
        t[p].lz * (t[p * 2 + 1].r - t[p * 2 + 1].l + 1);  //更新右儿子
    t[p * 2].lz += t[p].lz;
    t[p * 2 + 1].lz += t[p].lz;
    t[p].lz = 0;
  }
}

// 区间修改 [l,r]上每一个数都加x
// 例如修改[1,4]，可以拆成[1,3]和[4,4] [1,3]加上3*x, [4,4]加上1*x,
// 并分别加lz标记
void changeSeg(int p, int l, int r, int x) {
  if (l <= t[p].l && t[p].r <= r) {  // 完全包含
    t[p].dat += 1LL * (t[p].r - t[p].l + 1) * x;
    t[p].lz += x;
    return;
  }
  pushdown(p);
  int mid = (t[p].l + t[p].r) / 2;
  if (l <= mid)
    changeSeg(p * 2, l, r, x);
  if (r > mid)
    changeSeg(p * 2 + 1, l, r, x);
  t[p].dat = t[p * 2].dat + t[p * 2 + 1].dat;
}

// 区间查询  Q,l,r的指令，查询[l,r]上的最大值/和
ll ask(int p, int l, int r) {
  if (l <= t[p].l && r >= t[p].r)  //完全包含
    return t[p].dat;
  pushdown(p);
  int mid = (t[p].l + t[p].r) / 2;
  ll res = 0;
  if (l <= mid)
    res += ask(p * 2, l, r);
  if (r > mid)
    res += ask(p * 2 + 1, l, r);
  return res;
}

int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    cin >> a[i];
  build(1, 1, n);
  while (m--) {
    int id;
    cin >> id;
    if (id == 1) {
      int x, y, k;
      cin >> x >> y >> k;
      changeSeg(1, x, y, k);
    } else {
      int x, y;
      cin >> x >> y;
      cout << ask(1, x, y) << '\n';
    }
  }
  return 0;
}