树状数组-完整模板

一维树状数组

单点修改、区间查询

二维树状数组

区间修改、区间查询

#include<bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;
const int N=2222;
int t1[N][N],t2[N][N],t3[N][N],t4[N][N],n,m,op,lx,ly,rx,ry,v;
int lowbit(int x)
{
  return x&-x;
}
void add(int x,int y,int v)
{
  for(int nowx=x;nowx<=n;nowx+=lowbit(nowx))
  {
    for(int nowy=y;nowy<=m;nowy+=lowbit(nowy))
    {
      t1[nowx][nowy]+=v;
      t2[nowx][nowy]+=x*v;
      t3[nowx][nowy]+=y*v;
      t4[nowx][nowy]+=x*y*v;
    }
  }
}
void range_add(int lx,int ly,int rx,int ry,int v)
{
  add(lx,ly,v);
  add(lx,ry+1,-v);
  add(rx+1,ly,-v);
  add(rx+1,ry+1,v);
}
int ask(int x,int y)
{
  int ans=0;
  for(int nowx=x;nowx;nowx-=lowbit(nowx))
  {
    for(int nowy=y;nowy;nowy-=lowbit(nowy))
    {
      ans+= (x+1)*(y+1)*t1[nowx][nowy]
           -(y+1)*t2[nowx][nowy]
           -(x+1)*t3[nowx][nowy]
           +t4[nowx][nowy];
    }
  }
  return ans;
}
int range_ask(int lx,int ly,int rx,int ry)
{
  int sum1=ask(rx,ry),sum2=ask(rx,ly-1),sum3=ask(lx-1,ry),sum4=ask(lx-1,ly-1);
  return sum1-sum2-sum3+sum4;
}
main()
{
  cin>>n>>m;
  while( cin>>op )
  {
    if( op==1 )
    {
      cin>>lx>>ly>>rx>>ry>>v;
      range_add(lx,ly,rx,ry,v);
    }
    else{
      cin>>lx>>ly>>rx>>ry;
      cout<<range_ask(lx,ly,rx,ry)<<endl;
    }
  }

}