分塊

分塊是將線段樹的懶標記方法一般化，可證明通常情況下以$\sqrt{n}$分塊是最優解。

分塊思想核心： 整塊打包維護 碎塊逐個枚舉

int len,num;//len:每塊長度,num:分塊數量
int begin[],end[],pos[],sum[],add[];//begin,end:每塊的始末下標 pos:每個下標所屬塊 sum:每塊區間和 add:整塊增量標記
void init(){len=sqrt(n);num=n/len;if(n%len) num++;//處理尾部有碎塊情形for(int i=1;i<=num;i++){//獲取第i塊的首尾下標begin[i]=(i-1)*len+1;end[i]=i*len;}end[num]=n;//更新最后一碎塊尾下標for(int i=1;i<=n;i++) pos[i]=(i-1)/len+1;//獲取第i個下標所屬的塊for(int i=1;i<=num;i++)for(int j=begin[i];j<=end[i];j++)sum[i]+=a[j];//獲取每塊區間和
}

區間修改

以在$[l,r]$元素加d為例

extern int l,r,d,a[];
void update(){int beg=pos[l],ed=pos[r];//獲取l和r所屬的塊if(beg==ed){//l,r在相同塊中for(int i=l;i<=r;i++) a[i]+=d;sum[p]+=(r-l+1)*d;//更新該塊區間之和}else{//l,r中間跨越了整塊for(int i=l;i<=end[beg];i++) a[i]+=d;//將l所屬的塊處理完sum[beg]+=(end[beg]-l+1)*d;for(int i=beg+1;i<ed;i++) add[i]+=d;//處理中間的整塊for(int i=begin[ed];i<=r;i++) a[i]+=d;sum[ed]+=(r-begin[ed]+1)*d;}
}

總結：涉及到更新碎片，只在原數組a和塊區間和數組sum上更新，不更新add整塊增量標記

區間查詢

extern int l,r,a[];
int query(){int beg=pos[l],ed=pos[r];int ans=0;if(beg==ed){//l,r在相同塊中for(int i=l;i<=r;i++) ans+=a[i];ans+=add[p]*(r-l+1);//此塊可能被整體修改過}else{//l,r不在相同塊中for(int i=l;i<=end[l];i++) ans+=a[i];ans+=add[beg]*(end[l]-l+1);for(int i=beg+1;i<ed;i++) ans+=sum[i]+add[i]*(end[i]-begin[i]+1);//不能寫成add[i]*len,因為無法確定r是否在最后一個碎塊上for(int i=begin[ed];i<=r;i++) ans+=a[i];ans+=add[ed]*(r-begin[ed]+1);}return ans;
}