Peter_Matthew的博客

树状数组

2018-11-08

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));
}
}
}

使用支付宝打赏
使用微信打赏

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

扫描二维码,分享此文章