xhSong's Blog

新开的blog，也不知道写什么是好。

正好这几天在看树状数组方面的东西，这里就写些这方面的东西吧!

树状数组是一个查询和修改复杂度都为log(n)的数据结构。一般来说，树状数组用来解决区间求和问题。具体的算法过程这里就不介绍了。下面是一个动态查询区间和的程序：

#include <cstdio>
#define MAX 1000

int c[MAX+1];
int n;

int lowbit(int x)
{
    return x&(-x);
}

void change(int x,int k)
{
    while(x<=n){
        c[x]+=k;
        x=x+lowbit(x);
    }
}

int search(int x)
{
    int s=0;
    while(x>0){
        s+=c[x];
        x=x-lowbit(x);
    }
    return s;
}

int main()
{
    scanf("%d",&n);
    char s[3];
    int x,y,k;
    while(scanf("%s",&s)!=EOF){
        if(s[0]=='C' || s[0]=='c'){
            scanf("%d%d",&x,&k);
            change(x,k);
        }
        else if(s[0]=='Q' || s[0]=='q'){
            scanf("%d%d",&x,&y);
            printf("%d\n",search(y)-search(x-1));
        }
    }
    return 0;
}

Sample Input

10
Q 5 6
C 4 5
Q 1 5
C 7 9
Q 1 10
C 5 70
Q 3 10
Q 5 6

Sample Input

0
5
14
84
70
 

解释一下：

第一行的n表示我所开的数组大小，即数组为a[1...n]，数组元素初始值为0；

C x k 表示在数组元素a[x]每一个加上k，当然k可以是负数，那时候就是减操作了；

Q x y表示查询a[x]+ a[x+1]+...+a[y-1]+a[y]的值。

树状数组除了用于点修改区间查询，还可以进行区间修改点查询，下面是一维区间修改点查询的代码：

#include <cstdio>
#define  MAX 1000

int c[MAX +1 ]={0};
int n;

int lowbit(int x)
{
    return x&(-x);
}

void change (int x,int k)
{
    while(x>0){
        c[x]+=k;
        x=x-lowbit(x);
    }
}

int search(int x)
{
    int s=0;
    while(x<=n){
        s+=c[x];
        x=x+lowbit(x);
    }
    return s;
}

int main()
{
    scanf("%d",&n);
    char s[3];
    int x,y,k;
    while(scanf("%s",&s)!=EOF){
        if(s[0]=='C' || s[0]=='c'){
            scanf("%d%d%d",&x,&y,&k);
            change(y,k),change(x-1,-k);
        }
        else if(s[0]=='Q' || s[0]=='q'){
            scanf("%d",&x);
            printf("%d\n",search(x));
        }
    }
    return 0;
}

Sample Input

10
C 1 5 5
Q 3
C 3 4 -1
Q 3
4
Q 10
0
C 1 10 4
Q 7
4
Q 3
8
Q 5
9
C 1 2 7
Q 2
16
Q 4
8
 

Sample Output

5
4
0
4
8
9
16
8

同样也解释一下：

同上第一行的n表示我所开的数组大小

C x y k 表示将数组元素a[x...y]每一个加上k

Q x 表查询a[x]的值。

下面给出二维点修改区间（这时候就是面了）查询和二维区间修改点查询的代码：

二维点修改区间：

#include <cstdio>
#include <cstring>

#define MAX 100

int c[MAX+1][MAX+1];
int n,m;

int lowbit(int x)
{
    return x&(-x);
}

void change(int x,int y,int k)
{
    while(x<=n){
        int yy=y;
        while(yy<=m){
            c[x][yy]=c[x][yy]+k;
            yy+=lowbit(yy);
        }
        x+=lowbit(x);
    }
}

int search(int x,int y)
{
    int s=0;
    while(x>0){
        int yy=y;
        while(yy>0){
            s+=c[x][yy];
            yy-=lowbit(yy);
        }
        x-=lowbit(x);
    }
    return s;
}

int main()
{
    char s[3];
    int x1,y1,x2,y2,k;
    scanf("%d%d",&n,&m);
    memset(c,0,sizeof(c));
    while(scanf("%s",s)!=EOF){
        if(s[0]=='C' || s[0]=='c'){
            scanf("%d%d%d",&x1,&y1,&k);
            change(x1,y1,k);
        }
        else if(s[0]=='Q' || s[0]=='q'){
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            int s=search(x2,y2)-search(x2,y1-1)-search(x1-1,y2)+search(x1-1,y1-1);
            printf("%d\n",s);
        }
    }
    return 0;
}

二维区间修改点查询：

#include <cstdio>
#include <cstring>

#define MAX 100

int c[MAX+1][MAX+1];
int n,m;

int lowbit(int x)
{
    return x&(-x);
}

void change(int x,int y,int k)
{
    while(x>0){
        int yy=y;
        while(yy>0){
            c[x][yy]=c[x][yy]+k;
            yy-=lowbit(yy);
        }
        x-=lowbit(x);
    }
}

int search(int x,int y)
{
    int s=0;
    while(x<=n){
        int yy=y;
        while(yy<=m){
            s+=c[x][yy];
            yy+=lowbit(yy);
        }
        x+=lowbit(x);
    }
    return s;
}

int main()
{
    char s[3];
    int x1,y1,x2,y2,k;
    scanf("%d%d",&n,&m);
    memset(c,0,sizeof(c));
    while(scanf("%s",s)!=EOF){
        if(s[0]=='C' || s[0]=='c'){
            scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&k);
            change(x2,y2,k);
            change(x2,y1-1,-k);
            change(x1-1,y2,-k);
            change(x1-1,y1-1,k);
        }
        else if(s[0]=='Q' || s[0]=='q'){
            scanf("%d%d",&x1,&y1);
            printf("%d\n",search(x1,y1));
        }
    }
    return 0;
}

前几天做pku2155，先是用线段树，结果TLE……

后面直接套我给出的第四个版，2155 Accepted 4076K 454MS C++ 1190B

在加了点技巧——将二维数组c的类型int改成char，2155 Accepted 1136K 344MS C++ 1150B