Peter_Matthew的博客

树状数组

2018-11-08

本文共618字，大约需要阅读3分钟。 
1
2
3
4
int lowbit(int x)
{
    return x&(-x);
}

树状数组1

单点修改，区间查询。

1
2
//需要先
    add(i,a[i]);
1
2
3
4
5
6
void add(int x,long long d)
{
    for(;x<=nx;x+=lowbit(x))
        tree[x]+=d;
}
   add(x,k);
1
2
3
4
5
6
7
long long ask(int x)
{
    long long s;
    for(s=0;x;x-=lowbit(x))
        s+=tree[x];
    return s;
}
1
2
3
4
5
6
7
8
long long range_ask(int xa,int xb)
{
    long long s=0;
    s+=ask(xb);
    s-=ask(xa-1);
    return s;
}
    printf("%lld\n",range_ask(xa,xb));

完整代码如下：

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<bits/stdc++.h>
using namespace std;
long long tree[500005];
int nx;
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,long long d)
{
    for(;x<=nx;x+=lowbit(x))
        tree[x]+=d;
}
void range_add(int xa,int xb,long long d)
{
    add(xa,d);
    add(xb+1,-d);
}
long long ask(int x)
{
    long long s;
    for(s=0;x;x-=lowbit(x))
        s+=tree[x];
    return s;
}
long long range_ask(int xa,int xb)
{
    long long s=0;
    s+=ask(xb);
    s-=ask(xa-1);
    return s;
}
int q;
int main()
{
    scanf("%d%d",&nx,&q);
    for(int i=1,x;i<=nx;i++)
    {
        scanf("%d",&x);
        add(i,x);
    }
    for(int i=1,opt,x,xa,xb;i<=q;i++)
    {
        scanf("%d",&opt);
        if(opt==1)
        {
            long long k; 
            scanf("%d%lld",&x,&k);
            add(x,k);
        }
        if(opt==2)
        {
            scanf("%d%d",&xa,&xb);
            printf("%lld\n",range_ask(xa,xb));
        }
    }
}

树状数组2

区间修改，单点查询。

1
2
//需要先
    range_add(i,i,a[i]);
1
2
3
4
5
void add(int x,long long d)
{
    for(;x<=nx;x+=lowbit(x))
        tree[x]+=d;
}
1
2
3
4
5
6
void range_add(int xa,int xb,long long d)
{
    add(xa,d);
    add(xb+1,-d);
}
    range_add(xa,xb,k);
1
2
3
4
5
6
7
8
long long ask(int x)
{
    long long s;
    for(s=0;x;x-=lowbit(x))
        s+=tree[x];
    return s;
}
    printf("%lld\n",ask(x));

完整代码如下：

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<bits/stdc++.h>
using namespace std;
long long tree[500005];
int nx;
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,long long d)
{
    for(;x<=nx;x+=lowbit(x))
        tree[x]+=d;
}
void range_add(int xa,int xb,long long d)
{
    add(xa,d);
    add(xb+1,-d);
}
long long ask(int x)
{
    long long s;
    for(s=0;x;x-=lowbit(x))
        s+=tree[x];
    return s;
}
long long range_ask(int xa,int xb)
{
    long long s=0;
    s+=ask(xb);
    s-=ask(xa-1);
    return s;
}
int q;
int main()
{
    scanf("%d%d",&nx,&q);
    for(int i=1,x;i<=nx;i++)
    {
        scanf("%d",&x);
        range_add(i,i,x);
    }
    for(int i=1,opt,x,xa,xb;i<=q;i++)
    {
        scanf("%d",&opt);
        if(opt==1)
        {
            long long k;
            scanf("%d%d%lld",&xa,&xb,&k);
            range_add(xa,xb,k);
        }
        if(opt==2)
        {
            scanf("%d",&x);
            printf("%lld\n",ask(x));
        }
    }
}
当前页共有次阅读，条评论。
标签: 数据结构
← kmp 线段树 →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏