参考资料:
分块思想是一种广泛的思想,树状数组与线段树实际上都是使用了该种思想。但是,在实际问题中,我们常常会遇到一些更为灵活的问题,用线段树或者树状数组并不是那么好用。这里就需要我们化零为整,使用灵活分块的思想来解决。
举个例子,给定一数组,对其任意区间进行求和或者修改。假设该数组长度为N,我们可以选择以S为基准,将其分为N/S块,并记录每一分块的区间和Bi。虽然上式不一定是整除关系,但是并不重要。
讨论选定区间是否在同一块内的情况。如果在同一块内,直接进行块内修改与查询即可,时间复杂度为O(S);如果不在同一块,则查询修改区间被分为首和尾的不完整区间和中间的若干完整区间。我们对中间的完整区间进行成块修改查询,再对两端的不完整块进行查询修改,时间复杂度为O(N/S+S)。通过均值不等式易知当S=N0.5时间复杂度上界最优,为O(N0.5)。
解答上述例子的代码如下:
1 #include <cmath> 2 #include <iostream> 3 using namespace std; 4 const int N=5e4+5; 5 const int len=sqrt(N); 6 const int C=N/len+5; 7 int a[N],b[229],s[229];//a为原始数组,b记录每一块的和,s 8 int n,k; 9 void add (int l,int r,int num){ 10 int l_code = l/len; 11 int r_code = r/len; 12 if (r_code-l_code<=1){ 13 for (int i=l;i<=r;i++) 14 a[i]+=num; 15 } 16 else{ 17 for (int i=l;i<(l_code+1)*len;i++) 18 a[i]+=num; 19 for (int i=r_code*len;i<=r;i++) 20 a[i]+=num; 21 for (int i=l_code+1;i<=r_code-1;i++) 22 s[i]+=num; 23 } 24 } 25 int sum(int l,int r){ 26 int l_code = l/len; 27 int r_code = r/len; 28 int ans=0; 29 if (r_code-l_code==0){ 30 ans+=s[l_code]*(l-r); 31 for (int i=l;i<=r;i++) 32 ans+=a[i]; 33 return ans; 34 } 35 if (r_code-l_code==1){ 36 ans+=s[l_code]*((l_code+1)*len-l); 37 for (int i=l;i<(l_code+1)*len;i++) 38 ans+=a[i]; 39 ans+=s[r_code]*(r+1-(r_code)*len); 40 for (int i=r_code*len;i<=r;i++) 41 ans+=a[i]; 42 return ans; 43 } 44 if (r_code-l_code>1){ 45 ans+=s[l_code]*((l_code+1)*len-l); 46 for (int i=l;i<(l_code+1)*len;i++) 47 ans+=a[i]; 48 ans+=s[r_code]*(r+1-(r_code)*len); 49 for (int i=r_code*len;i<=r;i++) 50 ans+=a[i]; 51 for (int i=l_code+1;i<=r_code-1;i++) 52 ans+=(b[i]+s[i]*len); 53 return ans; 54 } 55 } 56 int main(){ 57 cin>>n; 58 int sum1=0; 59 for (int i=0;i<n;++i){ 60 cin>>a[i]; 61 if (i%len==(i-1)%len) 62 sum1+=a[i]; 63 else{ 64 b[k++]=sum1; 65 sum1=0; 66 } 67 } 68 b[k++]=sum1; 69 add(0,2,2);//需要测试的话自行修改,需注意数组下标从0开始 70 cout<<sum(1,4);//需要测试的话自行修改,需注意数组下标从0开始 71 return 0; 72 }
对于上述问题,进一步的优化方法可以对每个分块内部做前缀和,对于只需要查询的问题效果较好。
标签:code,int,len,块状,简述,sum1,数组,区间 From: https://www.cnblogs.com/johnsonstar/p/16999839.html