算法复习4.1分块

int block = sqrt(n);
int n= n/block;//注意不能直接sqrt（n）
if (n%block)t++;
for(int i=1;i<=t;i++)
{
  st[i]=(i-1)*block+1;
  ed[i]=i*block;
}
ed[t]=n;
for(int i=1;i<=n;i++)pos[i]=(i-1)/block+1

有些时候单纯写线段树错误率高（不想写）

void modify(int l,int r,int d){
  int p=pos[l],q=pos[r];
  if(p==q){
    for (int i=l;i<=r;i++)a[i]+=d;
    sum[p]+=d*(r-l+1;);
  }
  else
  {
    for(int i=p+1;i<=q-1){
      add[i]+=d;
    }
    for(int i=l;i<=ed[p];i++)a[i]+=d;
    sum[p]+=d*(ed[p]-l+1);
    for(int i=l;i<=st[q];i++)a[i]+=d;
    sum[q]+=d*(r-st[q]+1);
  }
}

int ask(int l,int r)
{
    int p=pos[l],q=pos[r];
    int ans=0;
    if(p==q){
    for (int i=l;i<=r;i++)ans+=a[i];
    ans+=add[i]*(r-l+1);
    }
    else
    for(int i=p+1;i<=q-1;i++)ans+=sum[i]+add[i]*(ed[i]-st[i]+1);
    for(i=l;i<=ed[p]i++)ans+=a[i];
    ans+=add[p]*(ed[p]-l+1);
    for (int i=st[q];i<=r;i++)ans+=a[i];
    ans +=add[q]*(r-st[q]+1)
    return ans;
}

，直接分块处理