分块板子

预处理

void init(){
    clean();
    scanf("%lld",&n);
    for(i=1;i<=n;i++)scanf("%lld",&a[i]);
    sq=sqrt(n);
    for(i=1;i<=sq;i++){
        st[i]=n/sq*(i-1)+1;
        ed[i]=n/sq*i;
    }
    ed[sq]=n;
    for(i=1;i<=sq;i++){
        for(j=st[i];j<=ed[i];j++)belong[j]=i,sum[i]+=a[j];
            size[i]=ed[i]-st[i]+1;
    }
  }

多测清空

void clean(){
    memset(sum,0,sizeof sum);//块的区间和 
    memset(mark,0,sizeof mark);//块标记 
    memset(st,0,sizeof st);//块的头 
    memset(ed,0,sizeof ed);//块尾 
    memset(belong,0,sizeof belong);//各点所在块编号 
    memset(a,0,sizeof a);//数组 
    memset(size,0,sizeof size);//各个块的元素总数 
}

单点加减

void ad(int x,int y){
    a[x]+=y;
    sum[belong[x]]+=y;
}

区间求和

int Sum(int l,int r){
   int ans=0;
   if(belong[l]==belong[r]){
      for(int i=l;i<=r;i++)ans+=(a[i]+mark[belong[l]]);
   }else{
      for(int i=l;i<=ed[belong[l]];i++)ans+=(a[i]+mark[belong[l]]);
      for(int i=st[belong[r]];i<=r;i++)ans+=(a[i]+mark[belong[r]]);
      for(int i=belong[l]+1;i<belong[r];i++)ans+=(sum[i]+1ll*mark[i]*size[i]);
   }
    return ans;
}

区间修改

void add(int l,int r,int val){
    if(belong[l]==belong[r]){
       for(int i=l;i<=r;i++){
	   a[i]+=val;
	   sum[belong[l]]+=val;
       }
     }else {
	 for(int i=l;i<=ed[belong[l]];i++){
	     a[i]+=val;
	     sum[belong[l]]+=val;
	 }
	 for(int i=st[belong[r]];i<=r;i++){
	    a[i]+=val;
	    sum[belong[r]]+=val;
	  }
	  for(int i=belong[l]+1;i<belong[r];i++)mark[i]+=val;
     }
}