題意：

有一個數組，有兩種操作。1: Q a b 求[a,b]的和 2：C a b c 給[a,b] 的所有元素都加上c。

題目：

You have?N?integers,?A1,?A2, ... ,?AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers?N?and?Q. 1 ≤N,Q?≤ 100000.
The second line contains?N?numbers, the initial values of?A1,?A2, ... ,?AN. -1000000000 ≤?Ai?≤ 1000000000.
Each of the next?Q?lines represents an operation.
"C?a?b?c" means adding?c?to each of?Aa,?Aa+1, ... ,?Ab. -10000 ≤?c?≤ 10000.
"Q?a?b" means querying the sum of?Aa,?Aa+1, ... ,Ab.

Output

You need to answer all?Q?commands in order. One answer in a line.

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

4
55
9
15

Hint

The sums may exceed the range of 32-bit integers.

題解：

區間求和加區間更新，典型的帶懶惰標記的線段樹。懶惰標記：更新的時候 并不將每個元素都更新，而是將要更新的區間打上懶惰標記，等下次要使用的時候 再向下更新。

線段樹的基本思想：二分，線段樹是一棵二叉搜索樹，它儲存的是一個區間的信息

算法思想：

1 。線段樹的成段更新--延遲更新;

2。區間查詢和更新的時候加入一個延遲節點;

3 。每次要在下次查詢或者更新到該區間時;

4 。再把節點的信息傳遞到左右孩子的結點上; 這樣更新大大減少了時間和空間上的開銷;

算法過程： 1 。每次更新并不需要更新到葉節點;

2 。只需更新到相應的段就可以了,然后記錄個add(懶惰標記);

3 。下次更新或者查詢的時候,如果要查到該段的子節點;

4 。就把add加到子節點上去,再將該add設為0; 這樣查詢子區間的復雜度就是更新的復雜度; 線段樹的基礎操作主要有5個：建樹、單點查詢、單點修改、區間查詢、區間修改。*/

有兩種解法：線段樹和樹狀數組

—，線段樹

/為了實現這個，引入一個新的狀態——懶標記。

1、直觀理解：“懶”標記，懶嘛！用到它才動，不用它就睡覺。

2、作用：存儲到這個節點的修改信息，暫時不把修改信息傳到子節點。就像家長扣零花錢，你用的時候才給你，不用不給你。 3、實現思路（重點）：a.原結構體中增加新的變量，存儲這個懶標記。 b.遞歸到這個節點時，只更新這個節點的狀態，并把當前的更改值累積到標記中。 注意是累積， c.什么時候才用到這個懶標記？當需要遞歸這個節點的子節點時，標記下傳給子節 點。這里不必管用哪個子節點，兩個都傳下去。

d.下傳操作： ①當前節點的懶標記累積到子節點的懶標記中。 ②修改子節點狀態。在引例中，就是原狀態+子節點區間點的個數*父節點傳下來的懶標記。 這就有疑問了，既然父節點都把標記傳下來了，為什么還要乘父節點的懶標記，乘自 己的不行嗎？ 因為自己的標記可能是父節點多次傳下來的累積，每次都乘自己的懶標記造成重復累積 ③父節點懶標記清0。這個懶標記已經傳下去了，不清0后面再用這個懶標記時會重復 下傳。

需要注意：1，懶惰標記數組一定要初始化。2. 數據范圍*4.

#include<cstdio> #include<cstring> #include<algorithm> #define inf 0x3f3f3f3f #define ll long long #define N 400010 //線段樹開4倍空間，有時需要離散化讓空間壓縮 using namespace std; ll Sum[N],add[N];//add 為懶惰標記，用到它才動，不用它就睡覺 void build(int l,int r,int o) {if(l==r)/*如果是葉子節點，存儲要維護的信息*/{scanf("%lld",&Sum[o]);return;}int mid=(l+r)>>1;/*對于二分到的每一個結點，給它的左右端點確定范圍。*/build(l,mid,o<<1);build(mid+1,r,o<<1|1);/*care 走左兒子mid+1*/Sum[o]=Sum[o<<1]+Sum[o<<1|1];//狀態合并,把當前結點的信息更新到父結點 } void pushdown(int o,int l)//把當前結點的信息更新給兒子結點 {if(add[o])//懶惰標記下移{/*such as 1—>7,變為1—>4{4-1+1}=(7-(7>>1))和5—>7{7-5+1}=(7>>1)*/add[o<<1]+=add[o];add[o<<1|1]+=add[o];Sum[o<<1]+=add[o]*(l-(l>>1)); //左子樹長度等于總長度減去右子樹長度Sum[o<<1|1]+=add[o]*(l>>1); //向下取整 右子樹的長度小于等于左子樹的長度add[o]=0;} } void update(int x,int y,int l,int r,int o,int c)//區間更新 {if(l>=x&&r<=y){Sum[o]+=c*(r-l+1);add[o]+=c;/*求和+=，若對值覆蓋=*/return;}pushdown(o,r-l+1);int mid=(l+r)>>1;if(x<=mid)update(x,y,l,mid,o<<1,c);if(y>mid)update(x,y,mid+1,r,o<<1|1,c);Sum[o]=Sum[o<<1]+Sum[o<<1|1];/*對節點數值進行維護*/ } ll query(int x,int y,int l,int r,int o)//區間查詢 {if(l>=x&&r<=y)/*用>=和<=,因為可能我們隨機生成的數，不在樹節點維護的區間上，若==導致死循環*/return Sum[o];pushdown(o,r-l+1);int mid=(l+r)>>1;ll sum=0;if(x<=mid)sum=query(x,y,l,mid,o<<1);if(y>mid)sum+=query(x,y,mid+1,r,o<<1|1);/*節點的數值等于左兒子加上右兒子的和*/return sum; } int main() {int n,m;while(~scanf("%d%d",&n,&m)){memset(Sum,0,sizeof(Sum));memset(add,0,sizeof(add));//將懶惰標記的值初始化為0build(1,n,1);while(m--){char str[10];int l,r,c;scanf("%s",str);if(str[0]=='Q'){scanf("%d%d",&l,&r);printf("%lld\n",query(l,r,1,n,1));}else{scanf("%d%d%d",&l,&r,&c);update(l,r,1,n,1,c);/*也可開結構體記錄1節點下標，節點維護區間*/}}} }

二，樹狀數組

區間更新 這就是第一個問題，如果題目是讓你把x-y區間內的所有值全部加上k或者減去k， 然后查詢操作是問某個點的值，這種時候該怎么做呢。如果是像上面的樹狀數組 來說，就必須把x-y區間內每個值都更新，這樣的復雜度肯定是不行的，這個時候 ，就不能再用數據的值建樹了，這里我們引入差分，利用差分建樹。 假設我們規定A[0] = 0; 則有 A[i] = Σij = 1D[j];(D[j] = A[j] - A[j-1])，即前面i項的差值和，這個有 什么用呢？例如對于下面這個數組 A[] = 1 2 3 5 6 9 D[] = 1 1 1 2 1 3 如果我們把[2,5]區間內值加上2，則變成了 A[] = 1 4 5 7 8 9 D[] = 1 3 1 2 1 1 發現了沒有，當某個區間[x,y]值改變了，區間內的差值是不變的，只有D[x]和D[y+1]的值發生改變 所以我們就可以利用這個性質對D[]數組建立樹狀數組, 區間查詢 上面我們說的差值建樹狀數組，得到的是某個點的值，那如果我既要區間更新，又 要區間查詢怎么辦。這里我們還是利用差分，由上面可知 則A[1]+A[2]+...+A[n] = (D[1]) + (D[1]+D[2]) + ... + (D[1]+D[2]+...+D[n]) = n*D[1] + (n-1)*D[2] +... +D[n] = n * (D[1]+D[2]+...+D[n]) - (0*D[1]+1*D[2]+...+(n-1)*D[n]) 如果你理解前面的都比較輕松的話，這里也就知道要干嘛了，維護兩個數狀數組， sum1[i] = D[i]，sum2[i] = D[i]*(i-1); #include<iostream> #include<string.h> #include<string> #define kk 100010 using namespace std; int n,m; long long a[kk],c[kk];///對應原數組和樹狀數組[表示差值](D[1] + D[2] + ... + D[n]) long long w[kk]; ///樹狀數組【要剪的差值（根據推出的公式）】(0*D[1] + 1*D[2] + ... + (n-1)*D[n]) void updata(int i,long long k) ///在i位置加上k {int x=i;//因為x不變，所以得先保存i值for(; i <= m; i+=i&(-i)){c[i] += k;w[i]+=k*(x-1);} } long long query(int i) ///求A[1 - i]的和(前綴和) {long long res = 0;int x=i;for(; i > 0; i-=i&(-i))res += x*c[i]-w[i];return res; } int main() {std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);while(cin>>m>>n){memset(a, 0, sizeof a);memset(c, 0, sizeof c);memset(w,0,sizeof(w));for(int i = 1; i <= m; i++){cin>>a[i];updata(i,a[i]-a[i-1]); ///輸入初值的時候，也相當于更新了值}string s;int x,y;long long z;while( n--){cin>>s;if(s[0] == 'Q') ///求和操作{cin>>x>>y;long long sum = query(y) - query(x-1); //x-y區間和也就等于1-y區間和減去1-(x-1)區間和cout << sum << endl;}else if(s[0] == 'C') ///[x,y]區間內加上z{cin>>x>>y>>z;updata(x,z);///A[x] - A[x-1]增加zupdata(y+1,-z); ///A[y+1] - A[y]減少z}}}return 0; } 這里利用的負數的存儲特性，負數是以補碼存儲的，對于整數運算 x&(-x)有 ● 當x為0時，即 0 & 0，結果為0； ●當x為奇數時，最后一個比特位為1，取反加1沒有進位，故x和-x除最后一位外前 面的位正好相反，按位與結果為0。結果為1。 ●當x為偶數，且為2的m次方時，x的二進制表示中只有一位是1（從右往左的第m+1 位），其右邊有m位0，故x取反加1后，從右到左第有m個0，第m+1位及其左邊全是1 。這樣，x& (-x) 得到的就是x。 ●當x為偶數，卻不為2的m次方的形式時，可以寫作x= y * (2^k)。其中，y的最低 位為1。實際上就是把x用一個奇數左移k位來表示。這時，x的二進制表示最右邊有 k個0，從右往左第k+1位為1。當對x取反時，最右邊的k位0變成1，第k+1位變為0 ；再加1，最右邊的k位就又變成了0，第k+1位因為進位的關系變成了1。左邊的位 因為沒有進位，正好和x原來對應的位上的值相反。二者按位與，得到：第k+1位上 為1，左邊右邊都為0。結果為2^k。 總結一下：x&(-x)，當x為0時結果為0；x為奇數時，結果為1；x為偶數時，結果為 x中2的最大次方的因子。 而且這個有一個專門的稱呼，叫做lowbit，即取2^k。

?

總結

以上是生活随笔為你收集整理的A Simple Problem with Integers POJ - 3468（线段树+区间查询+区间修改+建树+懒惰标记模板）+（树状数组）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。