原题链接：
解析：本题也是线段树的一种用法，算得上裸题，我用这题来加深对线段树的理解，以及熟悉线段树的模板。郭炜老师的代码是演示指针写法，但我更喜欢用数组来表示，所以改成了我喜欢的模板。
PS：刚刚刚刚刚才知道，这种方法是延迟标记，也就是说当对一端区间的叶子结点进行相同操作的时候，不要急着全部完成，不然递归等操作需要很多，我们可以记录对这个区间将要做什么操作，等查询的时候将所有对此区间的操作一次做完，这样就省的一次一次遍历了。举个例子，就比如对a进行+1操作，进行一千亿亿次，结果和+一千亿亿是一样的，然而效率却天差地别。
失误点：Query函数里的第一行，tree[root].l == s && tree[root].r == e，第一次将tree[root].r 写成tree[root].l，导致答案错误。
代码示例：
#include#include using namespace std;long long ans;struct Node{ int l,r; long long Inc; long long sum; int Mid(){ return (l+r)/2; }}tree[400050];void BuildTree(int root,int l,int r){ tree[root].l = l; tree[root].r = r; tree[root].sum = 0; tree[root].Inc = 0; if(l == r) return; int mid = (l+r)/2; BuildTree(2*root+1,l,mid); BuildTree(2*root+2,mid+1,r);}void Insert(int root,int i,int v){ if(tree[root].l == i && tree[root].r == i){ tree[root].sum = v; return; } tree[root].sum += v; if(i <= tree[root].Mid()) Insert(2*root+1,i,v); else Insert(2*root+2,i,v);}void Add(int root,int s,int e,long long c){ if(tree[root].l == s && tree[root].r == e){ tree[root].Inc += c; return; } tree[root].sum += c*(e-s+1); if(e <= tree[root].Mid()) Add(2*root+1,s,e,c); else if(s > tree[root].Mid()) Add(2*root+2,s,e,c); else{ Add(2*root+1,s,tree[root].Mid(),c); Add(2*root+2,tree[root].Mid()+1,e,c); }}long long Query(int root,int s,int e){ if(tree[root].l == s && tree[root].r == e){ return tree[root].sum + tree[root].Inc*(e-s+1); } tree[root].sum += tree[root].Inc*(tree[root].r - tree[root].l+1); Add(2*root+1,tree[root].l,tree[root].Mid(),tree[root].Inc); Add(2*root+2,tree[root].Mid()+1,tree[root].r,tree[root].Inc); tree[root].Inc = 0; if(e <= tree[root].Mid()) return Query(2*root+1,s,e); else if(s > tree[root].Mid()) return Query(2*root+2,s,e); else{ return Query(2*root+1,s,tree[root].Mid()) + Query(2*root+2,tree[root].Mid()+1,e); }}int main(){ int n,q,h; scanf("%d%d",&n,&q); BuildTree(0,1,n); for(int i = 1;i <= n;i++){ scanf("%d",&h); Insert(0,i,h); } char c[2]; for(int i = 0;i < q;i++){ scanf("%s",c); if(c[0] == 'Q'){ int s,e; scanf("%d%d",&s,&e); printf("%lld\n",Query(0,s,e)); }else{ int s,e,c; scanf("%d%d%d",&s,&e,&c); Add(0,s,e,c); } } return 0;}