树状数组

发表于 更新于

一、常用模板

1
2
3
4
5
6
7
8
9
10
11
12
13
// 一维树状数组，单点修改区间求和
const int maxn = 100015;
int B[maxn];
inline int lowbit(int x){return x&(-x);}
inline void zero(){memset(B,0,sizeof(B));}
inline void update(int i,int d){
    while(i<maxn) B[i]+= d, i +=lowbit(i);
}
inline int query(int i){
    int ret=0;
    while(i>0) ret+=B[i], i-=lowbit(i);
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 二维树状数组，单点修改矩阵求和
const int maxn = 1050;
int B[maxn][maxn];
inline int lowbit(int x){return x&(-x);}
inline void zero(){memset(B,0,sizeof(B));}
inline void update(int x,int y,int d){
    for(int i = x; i < maxn; i+=lowbit(i))
        for(int j = y; j < maxn; j+=lowbit(j)) B[i][j] += d;
}
inline int query(int x,int y){
    if(x <= 0 || y <= 0) return 0;
    int ans=0;
    for(int i = x; i > 0; i-=lowbit(i))
        for(int j = y; j > 0; j-=lowbit(j)) ans += B[i][j];
    return ans;
}
// 先传靠近原点的点
inline int query(int x1,int y1,int x2,int y2){ 
    return query(x2,y2) + query(x1-1,y1-1) - query(x2,y1-1) - query(x1-1,y2);
}

值得注意的是，树状数组也能在 $O(log(n))$ 复杂度内支持区间修改，区间求和操作,只需要将数据进行差分和对求和公式进行化简就好了(HDU1166)。

二、相关简单题

1、POJ2352

经典模板题，排序后直接套用数据结构，直接AC：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#define _CRT_SECURE_NO_WARNINGS
#include "cstdio"
#include "iostream"
#include "algorithm"
#include "cstring"

using namespace std;
const int MAX = 1000010;
int c[MAX] = {0};
int lowbit(const int& x){ return (x)&(-x); }
void zero() { memset(c, 0, sizeof(c)); }
// 一定要小心零的问题
void modify(int i, const int& d)
{
    while (i <= MAX)
    {
        c[i] += d;
        i += lowbit(i);
    }
}
int sum(int i)
{
    int ret = 0;
    while (i) {
        ret += c[i];
        i -= lowbit(i);
    }
    return ret;
}

int R[MAX] = { 0 };
int main()
{
    int N,x,y;
    scanf("%d",&N);
    for (int i = 0; i < N; ++i) {
        scanf("%d%d", &x, &y); ++x;
        ++R[sum(x)];
        modify(x, 1);
    }
    for (int i = 0; i < N; ++i) {
        printf("%d\n",R[i]);
    }
    return 0;
}

2、POJ3067

画图观察规律，排序直接套用模板(看了其他题解，做的时候没注意就是求逆序对):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include "iostream"
#include "cstring"
#include "cstdlib"
#include "algorithm"
using namespace std;
const int maxn = 1005;
int B[maxn];
inline int lowbit(int x){return x&(-x);}
inline void zero(){memset(B,0,sizeof(B));}
inline void update(int i,int d){
    while(i<maxn) B[i]+= d, i +=lowbit(i);
}
inline int query(int i){
    int ret=0;
    while(i>0) ret+=B[i], i-=lowbit(i);
    return ret;
}
struct P{
    int a,b;
    bool operator <(const P& p) const{
        if(p.a == a) return b < p.b;
        else return a < p.a;
    }
} nodes[maxn*maxn];
int main()
{
    int T,kase = 0;
    scanf("%d", &T);
    for(int i=1; i <= T; ++i){
        zero();
        int m,n,k;long long int ans=0;
        scanf("%d%d%d",&m,&n,&k);
        for(int j=0; j<k; ++j){
            scanf("%d%d",&nodes[j].a,&nodes[j].b);
        }
        sort(nodes,nodes+k);
        for(int j=0; j<k; ++j){
            update(nodes[j].b,1);       
            ans += query(n) - query(nodes[j].b);
        }
        printf("Test case %d: %lld\n", i,ans);
    }
    return 0;
}

3、⭐POJ3321

可以使用DFS遍历这颗树将这棵树线性化，例如：考虑到一颗7节点的满二叉树,DFS的遍历顺序为：12445523667731，显然，求根节点的子树和只需要求中间这一段244552366773的区间和。另一方面，对于本题，我们需要用链表前向构造这颗树，因此在遍历的过程中可能会丢失原始结构的顺序，在这里我们可以用DFS顺序来替代原始的结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include "iostream"
#include "cstring"
#include "cstdlib"
#include "algorithm"
using namespace std;
const int maxn = 100015;
int B[maxn];
inline int lowbit(int x){return x&(-x);}
inline void zero(){memset(B,0,sizeof(B));}
inline void update(int i,int d){
    while(i<maxn) B[i]+= d, i +=lowbit(i);
}
inline int query(int i){
    int ret=0;
    while(i>0) ret+=B[i], i-=lowbit(i);
    return ret;
}
// edge
struct E{
    int next,to;
} edges[maxn];
int heads[maxn],I[maxn],O[maxn],T[maxn];
int order = 0;
void dfs(int r)
{
    I[r] = ++order;update(order,1);
    for(int i= heads[r];i!=-1;i=edges[i].next) dfs(edges[i].to);
    O[r] = order;

}
int main()
{
    zero();
    int N,a,b,M;
    scanf("%d", &N);
    memset(heads,0xff,sizeof(heads));
    fill(T,T+N+5,1);
    for(int i = 1; i < N; ++i) {
        scanf("%d%d",&a,&b);
        edges[i-1].next = heads[a];
        edges[i-1].to = b;
        heads[a] = i - 1;
    }
    order = 1;dfs(1);
    char ops[10];
    scanf("%d",&M);
    for(int i = 0; i < M; ++i){
        scanf("%s%d",ops, &a);
        if(*ops == 'Q') printf("%d\n", query(O[a]) - query(I[a]-1));
        else if(T[a]) update(I[a],-1),T[a]^=1;
        else update(I[a],1),T[a]^=1;
    }

    return 0;
}

4、POJ1195

二维结构上的树状数组，非常简单，直接套用模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include "iostream"
#include "cstring"
#include "cstdlib"
#include "algorithm"
using namespace std;
const int maxn = 1050;
int B[maxn][maxn];
inline int lowbit(int x){return x&(-x);}
inline void zero(){memset(B,0,sizeof(B));}
inline void update(int x,int y,int d){
    for(int i = x; i < maxn; i+=lowbit(i))
        for(int j = y; j < maxn; j+=lowbit(j)) B[i][j] += d;
}
inline int query(int x,int y){
    if(x <= 0 || y <= 0) return 0;
    int ans=0;
    for(int i = x; i > 0; i-=lowbit(i))
        for(int j = y; j > 0; j-=lowbit(j)) ans += B[i][j];
    return ans;
}
inline int query(int x1,int y1,int x2,int y2){ 
    return query(x2,y2) + query(x1-1,y1-1) - query(x2,y1-1) - query(x1-1,y2);
}

int main()
{
    int op,x1,y1,a,x2,y2;
    while(~scanf("%d",&op)){
        if(op == 0) scanf("%d",&a),zero();
        else if(op == 1) scanf("%d%d%d",&x1,&y1,&a),update(x1+2,y1+2,a);
        else if(op == 2) scanf("%d%d%d%d",&x1,&y1,&x2,&y2),printf("%d\n",query(x1+2,y1+2,x2+2,y2+2));
        else return 0;
    }
    return 0;
}

5、HDU1166

刷错了，这是个线段树的练习题，不过用树状数组也能做。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include "iostream"
#include "cstring"
#include "cstdlib"
using namespace std;
const int maxn = 50005;
int B[maxn];
inline int lowbit(int x){return x&(-x);}
inline void zero(){memset(B,0,sizeof(B));}
inline void update(int i,int d){
    while(i<maxn) B[i]+= d, i +=lowbit(i);
}
inline int query(int i){
    if(i == 0) return 0;
    int ret=0;
    while(i>0) ret+=B[i], i-=lowbit(i);
    return ret;
}
char op[10];
int main()
{
    int T,kase = 0;
    scanf("%d", &T);
    while(T--){
        zero();
        int n,t,a,b;
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i){
            scanf("%d", &t);
            update(i, t);
        }

        printf("Case %d:\n", ++kase);
        while(true){
            scanf("%s", op);
            if(*op == 'Q'){
                scanf("%d%d",&a,&b);
                printf("%d\n", query(b) - query(a - 1));
            }else if(*op == 'A'){
                scanf("%d%d",&a,&b);
                update(a,b);
            }else if(*op == 'S'){
                scanf("%d%d",&a,&b);
                update(a,-b);
            }else{
                break;   
            }
        }

    }
    return 0;
}