[TIOJ 1869] 堆石子遊戲

原題：http://tioj.ck.tp.edu.tw/problems/1869
AC：http://tioj.ck.tp.edu.tw/submissions/25991

解題方向：二維BIT，分塊


題目大意：平面點修改值，平面查詢總和。

解法：二維BIT可以在$O(Q\log^2N)$輕鬆過這一題，如果要練$\sqrt N$分塊的話也是可以。

#include<bits/stdc++.h>
using namespace std;
int bbit[1025][1025];
int N;
inline void add(int v,int x,int y)
{
    while( x <= N )
    {
        for(int j=y;j<=N;j+=j&-j)
            bbit[x][j]+=v;
        x+=x&-x;
    }
}
inline int sum(int x,int y)
{
    int ans = 0;
    while( x )
    {        
        for(int j=y;j;j-=j&-j)
            ans+=bbit[x][j];
        x-=x&-x;
    }
    return ans;
}
int main()
{
    cin>>N;
    int mod,x1,y1,x2,y2,v;
    while(cin>>mod)
    {
        if( mod == 1 )
        {
            cin>>x1>>y1>>v;
            x1++;y1++;
            add(v,x1,y1);
        }
        else
        {
            cin>>x1>>y1>>x2>>y2;
            x1++;y1++;x2++;y2++;
            cout<< sum(x2,y2) - sum(x1-1,y2) - sum(x2,y1-1)+sum(x1-1,y1-1) <<'\n';
        }
    }
}