线段树成段更新需要用到延迟标记（或者说懒惰标记），简单来说就是每次更新的时候不要更新到底，用延迟标记使得更新延迟到下次需要更新or询问到的时候。延迟标记的意思是：这个区间的左右儿子都需要被更新，但是当前区间已经更新了。其主要使用了Lazy思想。
Lazy思想：lazy－tag思想，记录每一个线段树节点的变化值，当这部分线段的一致性被破坏我们就将这个变化值传递给子区间，大大增加了线段树的效率。
在此通俗的解释Lazy(t偷懒)的意思，比如现在需要对[a,b]区间值进行加c操作，那么就从根节点[1,n]开始调用update函数进行操作，如果刚好执行到一个子节点，它的节点标记为rt，这时tree[rt].l == a && tree[rt].r == b 这时我们可以一步更新此时rt节点的sum[rt]的值，sum[rt] += c * (tree[rt].r - tree[rt].l + 1)，注意关键的时刻来了，如果此时按照常规的线段树的update操作，这时候还应该更新rt子节点的sum[]值，而Lazy思想恰恰是暂时不更新rt子节点的sum[]值，到此就return，直到下次需要用到rt子节点的值的时候才去更新，这样避免许多可能无用的操作，从而节省时间 。
#define _CRT_SECURE_NO_DEPRECATE #include<iostream> #include<algorithm> const int MAXN = 100000+10; typedef long long LL; using namespace std; struct Tnode{ int b, e; LL sum; //当前区间和 LL mark; //延迟标记 }; Tnode tree[4*MAXN]; int n; void Build(int v, int b, int e){ tree[v].b = b, tree[v].e = e; tree[v].sum=tree[v].mark = 0; if (b < e){ int mid = (b + e) >> 1; Build(2 * v + 1, b, mid); Build(2 * v + 2, mid + 1, e); } } void update(int v, int l, int r, LL value){ if (l == tree[v].b&&r == tree[v].e){ tree[v].mark += value; //该区间每个数都要增加value，它的子区间可以先不更新(Lazy) return; //直接返回了 } tree[v].sum += value*(r - l + 1); //将增加的值更新进去 int mid = (tree[v].b + tree[v].e) >> 1; if (r <= mid) update(2 * v + 1, l, r, value); else if (l > mid) update(2 * v + 2, l, r, value); else{ update(2 * v + 1, l, mid, value); update(2 * v + 2, mid + 1, r, value); } } LL Qurrey(int v, int l, int r){ if (tree[v].b==l&&tree[v].e==r) return tree[v].sum+(r-l+1)*tree[v].mark; if (tree[v].mark != 0){ //之前欠的债现在要还了 //如果当前区间mark不为0，则将它传递给子区间 tree[2 * v + 1].mark += tree[v].mark; tree[2 * v + 2].mark += tree[v].mark; tree[v].sum += tree[v].mark*(tree[v].e-tree[v].b+1); tree[v].mark = 0; } int mid = (tree[v].b + tree[v].e) >> 1; if (r <= mid) return Qurrey(2 * v + 1, l, r); else if (l > mid) return Qurrey(2 * v + 2, l, r); else return Qurrey(2 * v + 1, l, mid) + Qurrey(2 * v + 2, mid + 1, r); } int main(){ long long x; int a, b,i,q; char ch; scanf("%d%d", &n, &q); Build(0, 1, n); for (i = 1; i <= n; i++){ scanf("%lld", &x); update(0, i, i, x); } while (q--){ cin >> ch; scanf("%d%d", &a, &b); if (ch == 'Q') printf("%lld ", Qurrey(0, a, b)); else{ scanf("%lld", &x); update(0, a, b, x); } } return 0; }