二维树状数组更块查点

在此不给予证明,但是证明很简单。

二维树状数组成块更新，查定点的值。

我们以一维的推广，我们可不可以成块更新转化为修改一些点的值，然后求点的值转化统计一块的和？

我们可以构造一个M矩阵，让M矩阵初始化为0，我们可以让坐标（x，y）的值等于以（1，1）和（x，y）组成的M子矩阵的元素之和（你看看，这个条件在刚开始的时候是成立的），我们更新以（x1，y1）和（x2，y2）组成的矩阵的值的时候，我们只需在M矩阵中插入（x1，y1）（x1，y2+1）（x2+1，y1）（x2+1，y2+1）的值。

比如我们将以（x1，y1）和（x2，y2）组成的矩阵的元素都加上val。那么我们将（x1，y1）+val，（x1，y2+1）-val，（x2+1，y1）-val，（x2+1，y2+1）+val即可。

题意：对一个n∗m的矩阵进行一些操作和查询，操作：成块修改。查询：求某个元素的值，

#include<bits/stdc++.h>
using namespace std;
int bt[1100][1100];
int MAXN,MAXM;//矩阵的行和列
int lowbit(int k)
{
    return k&-k;
}
void modify(int x,int y,int val){//更新所有与他有关的节点
    for(int i=x;i<=MAXN;i+=lowbit(i)){
        for(int j=y;j<=MAXM;j+=lowbit(j))
            bt[i][j]+=val;
    }
}
int getsum(int x,int y)//等于其左上角矩阵的和
{
    int ans=0;
    for(int i=x;i>0;i-=lowbit(i)){
        for(int j=y;j>0;j-=lowbit(j))
            ans+=bt[i][j];
    }
    return ans;
}
void update(int x1,int y1,int x2,int y2,int val)//更新差值矩阵
{
    modify(x1,y1,val);
    modify(x1,y2+1,-val);
    modify(x2+1,y1,-val);
    modify(x2+1,y2+1,val);
}
int main()
{
    int q,val,x,y,x1,y1,x2,y2;
    cin>>MAXN>>MAXM;
    cin>>q;
    while(q--){//修改操作
        cin>>x1>>y1>>x2>>y2>>val;
        update(x1,y1,x2,y2,val);
    }
    cin>>q;//查询操作的次数
    while(q--)
    {
        cin>>x>>y;
        int ans=getsum(x,y);
        cout<<ans<<endl;
    }
}