树状数组
解决什么问题?
- 给某个位置上的数，加上一个数。(单点修改)
- 求某一个前缀和。（区间查询）
时间复杂度
步骤及实现
给定一个数组{1,5,7,11,4,3,2,6,11,21,15,17,14,13,20,35}。下面将通过树状数组的方式进行查询与修改。
把普通数组进行存储。
存储的位置，从数组的下标”1”开始存，下标”0”不存储元素。
把普通数组转换成树状数组（重点）。
看不懂没关系，先给大家讲解一下，单点修改和区间查询是如何方便的：
“前缀和”的单点修改对整体数组修改的影响
假如我们对一个数组的下标3的元素进行加3操作，那么它对应的前缀和数组，下标3之后的所有元素都要进行加3操作，这样操作的时间开销是极大的。
如果使用树状数组，对下标3的元素进行加3操作，树状数组的开销就小得多。
仅对下标为“3”,”4”,”8 “,“16”的元素进行加3操作。
- 下面是最终转换的树状数组：
- 构建树状数组的代码如下：
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
|
#include<iostream>
using namespace std;
int n;
const int N=100005;
int a[N],tr[N];
int lowbit(int x)
{
return x & -x;
}
void add(int x,int v)
{
for(int i=x;i<=n;i+=lowbit(i))
{
tr[i]+=v;
}
}
int query(int x)
{
int res=0;
for(int i=x;i;i-=lowbit(i))
{
res+=tr[i];
}
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++)
{
add(i,a[i]);
}
for(int i=1;i<=n;i++)
{
printf("%d ",tr[i]);
}
return 0;
}
|
- 在某个位置加上一个数，并且查询某个某个区间的前缀和。
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
#include<iostream>
using namespace std;
int n,m;
const int N=100005;
int a[N],tr[N];
int lowbit(int x)
{
return x & -x;
}
void add(int x,int v)
{
for(int i=x;i<=n;i+=lowbit(i))
{
tr[i]+=v;
}
}
int query(int x)
{
int res=0;
for(int i=x;i;i-=lowbit(i))
{
res+=tr[i];
}
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++)
{
add(i,a[i]);
}
scanf("%d",&m);
while(m--)
{
int k,x,y;
scanf("%d%d%d",&k,&x,&y);
if(k==1)
{
add(x,y);
}else
{
printf("%d\n",query(y)-query(x-1));
}
}
return 0;
}
|
线段树
解决什么问题?
时间复杂度
- 修改：O(long n)
- 查询：O(4long n)
步骤及实现
给定一个数组{1,2,3,4,5,6,7}。下面将通过线段树的方式进行查询与修改。
- 把普通数组进行存储。
存储的位置，从数组的下标”1”开始存，下标”0”不存储元素。
- 把普通数组转换成线段树（重点）。
- 线段树代码
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
#include<iostream>
using namespace std;
int n,m;
const int N=100005;
int w[N];
struct Node
{
int l,r;
int sum;
}tr[N*4];
void pushup(int u)
{
tr[u].sum = tr[u<<1].sum+tr[u<<1|1].sum;
}
void build(int u,int l,int r)
{
if(l==r)
{
tr[u]={l,r,w[r]};
}else
{
tr[u]={l,r};
int mid = l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
}
int query(int u,int l,int r)
{
if(tr[u].l>=l &&tr[u].r<=r)
{
return tr[u].sum;
}
int mid = tr[u].l+tr[u].r>>1;
int sum=0;
if(l<=mid)
{
sum=query(u<<1,l,r);
}
if(r>mid)
{
sum+=query(u<<1|1,l,r);
}
return sum;
}
void modify(int u,int x,int v)
{
if(tr[u].l==tr[u].r)
{
tr[u].sum+=v;
}else
{
int mid = tr[u].l+tr[u].r>>1;
if(x<=mid)
{
modify(u << 1, x, v);
}else
{
modify(u << 1 | 1, x, v);
}
pushup(u);
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>w[i];
}
build(1,1,n);
cin>>m;
while(m--)
{
int k,x,y;
cin>>k>>x>>y;
if(k == 1)
{
modify(1,x,y);
}else
{
cout<<query(1,x,y)<<endl;
}
}
}
|
