代码源数据结构中级课
第一课：树状数组笔记
目录- 树状数组1
- 树状数组2
- 逆序对2
- 树状数组二分
- 二维树状数组
思路：
l
o
w
b
i
t
lowbit
lowbit：求二进制数最低位
1
1
1和尾端
0
0
0构成的二进制数，
l
o
w
b
i
t
(
x
)
=
x
&
(
−
x
)
lowbit(x)=x\&(-x)
lowbit(x)=x&(−x)
树状数组
c
i
=
∑
j
=
i
−
l
o
w
b
i
t
(
i
)
+
1
i
a
j
c_i=\sum_{j=i-lowbit(i)+1}^ia_{j}
ci=∑j=i−lowbit(i)+1iaj
单点加：
void modify(int x,ll val){
for(;x<=n;x+=x&(-x)) c[i]+=val;
}
前缀和查询：
ll query(int x){
ll s=0;
for(;x;x-=x&(-x)) s+=c[i];
return s;
}
在此基础上修改 a x = d a_x=d ax=d，只需要： m o d i f y ( x , d − a [ x ] ) , a [ x ] = d modify(x,d-a[x]),a[x]=d modify(x,d−a[x]),a[x]=d即可
C o d e : Code: Code:
#include 思路：考虑差分，对
[
l
,
r
]
[l,r]
[l,r]的区间都加上
d
d
d，只需要在差分数组
d
[
l
]
d[l]
d[l]处
+
d
+d
+d，
d
[
r
+
1
]
d[r+1]
d[r+1]处
−
d
-d
−d
原数组和差分数组对应关系为：
a
i
=
∑
k
=
1
i
d
k
a_i=\sum_{k=1}^{i} d_k
ai=∑k=1idk
那么
∑
i
=
1
x
a
i
=
∑
i
=
1
x
(
x
+
1
−
i
)
∗
d
i
=
(
x
+
1
)
∑
i
=
1
x
d
i
−
∑
i
=
1
x
i
∗
d
i
\sum_{i=1}^x a_i=\sum_{i=1}^x (x+1-i)*d_i=(x+1)\sum_{i=1}^xd_i-\sum_{i=1}^x i*d_i
∑i=1xai=∑i=1x(x+1−i)∗di=(x+1)∑i=1xdi−∑i=1xi∗di
对于
∑
i
=
1
x
d
i
\sum_{i=1}^xd_i
∑i=1xdi，
∑
i
=
1
x
i
∗
d
i
\sum_{i=1}^x i*d_i
∑i=1xi∗di，维护两个树状数组即可
C o d e : Code: Code:
#include 思路：把静态问题转化为动态问题+权值开树状数组
对于
j
j
j从
[
1
,
n
]
[1,n]
[1,n]循环的时候，统计
a
[
1
,
j
−
1
]
a_{[1,j-1]}
a[1,j−1]中大于
a
j
a_j
aj的个数，对于
a
[
1
,
j
−
1
]
a_{[1,j-1]}
a[1,j−1]维护一个数据结构
D
D
D，统计完个数之后再将
a
j
a_j
aj加入
D
D
D中
那么
D
D
D满足的 *** 作为：
1.
D
[
a
x
]
+
=
1
1.D[a_x]+=1
1.D[ax]+=1，
2.
2.
2.后缀和查询
理解为把
a
x
a_x
ax当作下标加入
D
D
D中，那么对于
a
[
1
,
x
−
1
]
a_{[1,x-1]}
a[1,x−1]中在
D
D
D中在
a
x
a_x
ax后面的和即为
a
[
1
,
x
−
1
]
a_{[1,x-1]}
a[1,x−1]中比
a
x
a_x
ax大的数的个数，对于这个后缀和查询，只要预处理
a
i
=
n
+
1
−
a
i
a_i=n+1-a_i
ai=n+1−ai即可转化为前缀和查询
C o d e ： Code： Code：
#include 思路：直接二分的复杂度为
O
(
l
o
g
2
n
)
O(log^2n)
O(log2n)，如果在
q
u
e
r
y
query
query时，从最高位开始向最低位循环，如果满足
c
[
p
o
s
+
(
1
<
<
j
)
]
<
=
s
c[pos+(1<
C o d e : Code: Code:
#include 思路： k k k维树状数组的复杂度为 O ( l o g k n ) O(log^kn) O(logkn)
C o d e : Code: Code:
#include 欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）