[cpp] /*********************************************** 題目大意: Q a b ：查詢區間[a,b]的和; C a b x : 更新區間[a,b]，區間所有值加上x; 算法思想： 線段樹的成段更新--延遲更新; 在區間查詢和更新的時候加入一個延遲節點; 每次要在下次查詢或者更新到該區間時; 再把節點的信息傳遞到左右孩子的結點上; 這樣更新大大減少了時間和空間上的開銷; 算法過程： 每次更新並不需要更新到葉節點; 只需更新到相應的段就可以了,然後記錄個add; 下次更新或者查詢的時候,如果要查到該段的子節點; 就把add加到子節點上去,再將該add設為0; 這樣查詢子區間的復雜度就是更新的復雜度; ************************************************/ #include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<climits> #include<algorithm> using namespace std; #define L l , m , u << 1 #define R m + 1 , r , u << 1 | 1 typedef long long LL; const int N = 111111; LL add[N<<2]; LL sum[N<<2]; void PushUp(int u)//把當前結點的信息更新到父結點 { sum[u] = sum[u<<1] + sum[u<<1|1]; } void PushDown(int u,int m)//把當前結點的信息更新給兒子結點 { if (add[u]) { add[u<<1] += add[u]; add[u<<1|1] += add[u]; sum[u<<1] += add[u] * (m - (m >> 1)); sum[u<<1|1] += add[u] * (m >> 1); add[u] = 0; } } void build(int l,int r,int u) { add[u] = 0; if (l == r) { scanf("%lld",&sum[u]); return ; } int m = (l + r) >> 1; build(L); build(R); PushUp(u); } void update(int l1,int r1,int c,int l,int r,int u) { if (l1 <= l && r <= r1) { add[u] += c; sum[u] += (LL)c * (r - l + 1); return ; } PushDown(u , r - l + 1); int m = (l + r) >> 1; if (l1 <= m) update(l1 , r1 , c , L); if (m < r1) update(l1 , r1 , c , R); PushUp(u); } LL query(int l1,int r1,int l,int r,int u) { if (l1 <= l && r <= r1) { return sum[u]; } PushDown(u , r - l + 1); int m = (l + r) >> 1; LL res = 0; if (l1<= m) res += query(l1 , r1 , L); if (m < r1) res += query(l1 , r1 , R); return res; } int main() { //freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin); int N , Q; scanf("%d%d",&N,&Q); build(1 , N , 1); while (Q--) { char op[2]; int a , b , c; scanf("%s",op); if (op[0] == 'Q') { scanf("%d%d",&a,&b); printf("%lld\n",query(a , b , 1 , N , 1)); } else { scanf("%d%d%d",&a,&b,&c); update(a , b , c , 1 , N , 1); } } return 0; }
