題意：有n個數和兩種操作,C A B C和 Q AＢ，“C A B C”表示區間Ａ～Ｂ的數均增加Ｃ， Q AＢ表示詢問區間Ａ～Ｂ的和。
思路：
是典型的線段樹成段更新和區間求和問題。不過我被書上誤導了，導致調試了一下午，最後搞得特暈。所以，還是要相信自己的想法，不要完全依賴別人的。。。
區間線段更新時，有向上更新（父節點）和向下更新（子節點）。一定要理解好它。當對某一區間更新時，比如更新
［１，３］，同時它的父節點［１，５］也要更新。向下更新即當前區間不能被要更新區間完全覆蓋，那麼就要把當前區間的公共增量向左右子樹傳遞，並把當前區間的增量改為０，同時左右子樹的ｓｕｍ值也要改變，ａｄｄ的改變和ｓｕｍ的改變的同步的。
#include#include #define LL long long const int maxn = 100005; __int64 a[maxn]; struct line { int l; int r; LL sum,add;//增加兩個區域，一個記錄區間之和，一個記錄區間公共增量 }tree[maxn<<2]; void build(int v, int l, int r) { tree[v].l = l; tree[v].r = r; tree[v].add = 0; if(l == r) { tree[v].sum = a[r]; return; } int mid = (l+r)>>1; build(v*2,l,mid); build(v*2+1,mid+1,r); tree[v].sum = tree[v*2].sum + tree[v*2+1].sum; } void update(int v, int l, int r,__int64 add) //更新區間l~r分別加上add; { tree[v].sum += (r-l+1)*add;//不論該區間是否是要更新區間，肯定是當前區間的子區間，所以也要更新當前區間sum值。 if(tree[v].l == l && tree[v].r == r)//如果當前區間恰好被要更新區間完全覆蓋，那麼用add維護當前區間公共增量，不必往下更新了。 { tree[v].add += add; //注意是 +=,因為節點本身也有增量 return; } int mid = (tree[v].l + tree[v].r)>>1; if(tree[v].add) //如果上面沒有走掉，就把增量向下傳遞，注意傳遞增量的同時左右子樹的sum值也要改變 { tree[v*2].add += tree[v].add; tree[v*2+1].add += tree[v].add; tree[v*2].sum += tree[v].add * (tree[v*2].r-tree[v*2].l+1); tree[v*2+1].sum += tree[v].add * (tree[v*2+1].r-tree[v*2+1].l+1); tree[v].add = 0; } if(r <= mid) update(v*2,l,r,add); else { if(l > mid) update(v*2+1,l,r,add); else { update(v*2,l,mid,add); update(v*2+1,mid+1,r,add); } } } __int64 query(int v, int l, int r) { if(tree[v].l == l && tree[v].r == r) return tree[v].sum; int mid = (tree[v].l + tree[v].r)>>1; if(tree[v].add)//上面沒走掉，同樣增量向下傳遞，子樹的sum值也在改變。 { tree[v*2].add += tree[v].add; tree[v*2+1].add += tree[v].add; tree[v*2].sum += tree[v].add * (tree[v*2].r-tree[v*2].l+1); tree[v*2+1].sum += tree[v].add * (tree[v*2+1].r-tree[v*2+1].l+1); tree[v].add = 0; } if(r <= mid) query(v*2,l,r); else { if(l > mid) return query(v*2+1,l,r); else return query(v*2,l,mid)+ query(v*2+1,mid+1,r); } } int main() { int n,m; char ch[2]; int l,r; __int64 ans,add; scanf(%d %d,&n,&m); for(int i = 1; i <= n; i++) scanf(%I64d,&a[i]); build(1,1,n); while(m--) { scanf(%s,ch); if(ch[0] == 'C') { scanf(%d %d %I64d,&l,&r,&add); update(1,l,r,add); } else { scanf(%d %d,&l,&r); ans = query(1,l,r); printf(%I64d ,ans); } } return 0; }
