学步园

思路：二维线段树。每次询问输出一个矩阵范围内的和。

用树套树写的。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2005
#define inf 1<<28
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
using namespace std;
inline void readint(int &ret)
{
    char c;
    do
    {
        c = getchar();
    }
    while(c < '0' || c > '9');
    ret = c - '0';
    while((c=getchar()) >= '0' && c <= '9')
        ret = ret * 10 + ( c - '0' );
}
int n ;
struct treey
{
    int l , r ,sum ;
    int getmid(){
        return ((l + r) / 2);
    }
} ;
struct treex
{
    int l ,r ;
    int getmid(){
        return ((l + r) / 2) ;
    }
    treey y[1111 * 4] ;
}tree[1111 * 4] ;

void buildy(int l ,int r ,int posx, int posy)
{
    tree[posx].y[posy].l = l ;
    tree[posx].y[posy].r = r ;
    tree[posx].y[posy].sum = 0 ;
    if(l == r )return ;
    int mid = tree[posx].y[posy].getmid() ;
    buildy(l , mid , posx ,LL(posy)) ;
    buildy(mid + 1 , r , posx ,RR(posy)) ;
}

void buildx(int l ,int r ,int pos)
{
    buildy(0,n,pos,1) ;
    tree[pos].l = l ;
    tree[pos].r = r ;
    if(l == r)return ;
    int mid = tree[pos].getmid() ;
    buildx(l,mid ,LL(pos)) ;
    buildx(mid + 1 ,r ,RR(pos)) ;
}

void updatay(int y ,int count ,int posx ,int posy)
{
    tree[posx].y[posy].sum += count ;
    if(tree[posx].y[posy].l == tree[posx].y[posy].r)return ;
    int mid = tree[posx].y[posy].getmid() ;
    if(y <= mid)updatay(y,count,posx,LL(posy)) ;
    else updatay(y,count,posx,RR(posy)) ;
}

void updatax(int l ,int r ,int count ,int pos)
{
    updatay(r,count,pos,1) ;
    if(tree[pos].l == tree[pos].r)return ;
    int mid = tree[pos].getmid() ;
    if(l <= mid)updatax(l,r,count,LL(pos)) ;
    else updatax(l,r,count,RR(pos)) ;
}

int query_y(int x ,int y ,int posx,int posy)
{
    if(tree[posx].y[posy].l == x && tree[posx].y[posy].r == y)return tree[posx].y[posy].sum ;
    int mid = tree[posx].y[posy].getmid() ;
    if(y <= mid)return query_y(x,y,posx,LL(posy)) ;
    else if(x > mid)return query_y(x,y,posx,RR(posy)) ;
    else return query_y(x,mid ,posx,LL(posy)) + query_y(mid + 1 ,y ,posx,RR(posy)) ;
}

int query_x(int lx ,int ly ,int rx ,int ry,int pos)
{
    if(tree[pos].l == lx && tree[pos].r == ly)
    return query_y(rx,ry,pos,1) ;
    int mid = tree[pos].getmid() ;
    if(ly <= mid)return query_x(lx,ly,rx,ry,LL(pos)) ;
    else if(lx > mid)return query_x(lx,ly,rx,ry,RR(pos)) ;
    else return query_x(lx,mid,rx,ry,LL(pos)) + query_x(mid + 1 , ly ,rx,ry,RR(pos)) ;
}
int main()
{
    int op ;
    while(scanf("%d",&op))
    {
        if(op == 3)break ;
        if(op == 0)
        {
            readint(n) ;
            buildx(0,n,1) ;
        }
        if(op == 1)
        {
            int x ,y , z ;
            readint(x) ;
            readint(y) ;
            scanf("%d",&z) ;
            updatax(x,y,z,1) ;
        }
        if(op == 2)
        {
            int x ,xx ,y ,yy ;
            readint(x) ;
            readint(xx) ;
            readint(y) ;
            readint(yy) ;
            printf("%d\n",query_x(x,y,xx,yy,1)) ;
        }
    }
    return 0;
}

二维树状数组，比树套树快。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2005
#define inf 2000000000
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
using namespace std;
inline void RD(int &ret)
{
    char c;
    do
    {
        c = getchar();
    }
    while(c < '0' || c > '9');
    ret = c - '0';
    while((c=getchar()) >= '0' && c <= '9')
        ret = ret * 10 + ( c - '0' );
}
int lowbit(int x )
{
    return x & (-x) ;
}
int n , m ;
ll a[1555][1555] ;
void add(int x ,int y ,int num)
{
    for (int i = x ;i <= n ;i += lowbit(i))
        for (int j = y ; j <= m ;j += lowbit(j) )
            a[i][j] += num ;
}
ll sum(int x ,int y )
{
    ll ans = 0ll ;
    for (int i = x ;i > 0 ;i -= lowbit(i))
        for (int j = y ;j > 0 ; j -= lowbit(j))
            ans += a[i][j] ;
    return ans ;
}
ll getsum(int x1, int y1, int x2 ,int y2)
{
    return sum(x2,y2) + sum(x1 - 1,y1 - 1) - sum(x1 - 1,y2) - sum(x2,y1 - 1) ;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("acm.txt", "r", stdin);
#endif
    int op ;
    while(1)
    {
        RD(op) ;
        if(!op){
            RD(n) ;
            n ++ ;
            m = n ;
            mem(a,0) ;
        }
        else if(op == 1){
            int x ,y ,num ;
            RD(x) ;RD(y) ;
            scanf("%d",&num) ;
            x ++ ,y ++ ;
            add(x,y,num) ;
        }
        else if(op == 2){
            int x1 ,y1 ,x2 ,y2 ;
            RD(x1) ;RD(y1) ;RD(x2) ;RD(y2) ;
            x1 ++ , x2 ++ ,y1 ++ ,y2 ++ ;
            printf("%lld\n",getsum(x1,y1,x2,y2)) ;
        }
        else if(op == 3)break ;
    }
    return 0;
}

——13.06.16更新