分塊之區間修改與單點查詢

給出一個長為n的數列，以及n個操作，操作涉及區間加法，單點查值。

這是一道能用許多數據結構優化的經典題，可以用於不同數據結構訓練。

數列分塊就是把數列中每m個元素打包起來，達到優化演算法的目的。

以此題為例，如果我們把每m個元素分為一塊，共有n/m塊，每次區間加的操作會涉及O(n/m)個整塊，以及區間兩側兩個不完整的塊中至多2m個元素。

我們給每個塊設置一個加法標記（就是記錄這個塊中元素一起加了多少），每次操作對每個整塊直接O(1)標記，而不完整的塊由於元素比較少，暴力修改元素的值。

每次詢問時返回元素的值加上其所在塊的加法標記。

這樣每次操作的複雜度是O(n/m)+O(m)，根據均值不等式，當m取√n時總複雜度最低，為了方便，我們都預設下文的分塊大小為√n。

區間加法

 1 void interval_add(int ll,int rr,int v)
 2 {
 3     for(int i=ll;i<=min(where[ll]*m,rr);i++)
 4     //這裡判斷的是where[ll]是不完全塊的情況，也就是ll在他實際塊最左端的右側，
 5     // 然後便利ll-所在塊的結尾/rr，暴力增加 
 6         a[i]+=v; 
 7     if(where[ll]!=where[rr])
 8     // 註意如果是ll和rr在一個塊中的話，上面已經加過一邊，所以不用加 
 9     {
10         for(int i=(where[rr]-1)*m;i<=rr;i++)
11         // 這裡判斷的是rr在他實際所在塊的最右端左側的情況
12         // where[i]*m表示的是第i個塊最右端的元素
13         // where[rr]-1就是rr所在塊左邊那個塊最右端的元素
14         // 一直到rr暴力增加 
15             a[i]+=v;    
16     }    
17     for(int i=where[ll]+1;i<=where[rr]-1;i++)
18     //這裡where[ll]和where[rr]均已暴力處理過，所以只枚舉中間的塊就可以 
19         add[i]+=v;
20 } 

單點查詢

 1 printf("%d\n",a[v]+add[where[v]]); 

完整代碼

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 const int MAXN=100001;
 7 int n,q,m,how,l,r,v;
 8 int a[MAXN];// 初始值
 9 int add[MAXN];// 後來每個塊上加入的值
10 int where[MAXN];// 記錄每一個值對應第幾塊
11 void interval_add(int ll,int rr,int v)
12 {
13     for(int i=ll;i<=min(where[ll]*m,rr);i++)
14     //這裡判斷的是where[ll]是不完全塊的情況，也就是ll在他實際塊最左端的右側，
15     // 然後便利ll-所在塊的結尾/rr，暴力增加 
16         a[i]+=v; 
17     if(where[ll]!=where[rr])
18     // 註意如果是ll和rr在一個塊中的話，上面已經加過一邊，所以不用加 
19     {
20         for(int i=(where[rr]-1)*m;i<=rr;i++)
21         // 這裡判斷的是rr在他實際所在塊的最右端左側的情況
22         // where[i]*m表示的是第i個塊最右端的元素
23         // where[rr]-1就是rr所在塊左邊那個塊最右端的元素
24         // 一直到rr暴力增加 
25             a[i]+=v;    
26     }    
27     for(int i=where[ll]+1;i<=where[rr]-1;i++)
28     //這裡where[ll]和where[rr]均已暴力處理過，所以只枚舉中間的塊就可以 
29         add[i]+=v;
30 } 
31 int main()
32 {
33     scanf("%d",&n);
34     m=sqrt(n);
35     for(int i=1;i<=n;i++)
36         scanf("%d",&a[i]);
37     for(int i=1;i<=n;i++)
38         where[i]=(i-1)/m+1;// 這裡的i可以-1(hzwer寫的是-1)也可以不寫，不寫的話第一塊的元素個數會是m-1 
39     scanf("%d",&q);
40     for(int i=1;i<=q;i++)
41     {
42         scanf("%d",&how);
43         if(how==1)// 區間加
44         {
45             scanf("%d%d%d",&l,&r,&v);
46             interval_add(l,r,v);
47         }
48         else// 單點查詢 
49         {
50             scanf("%d",&v);
51             printf("%d\n",a[v]+add[where[v]]);
52             // where保存的是這個點所屬的塊，add表示這個塊已經增加的元素
53             //a[v]是這個點開始的值，一加就是答案 
54         } 
55     }
56     return 0;
57 }