树状数组用途 |
---|
单点增加 |
求逆序对 |
动态维护前缀和 |
树状数组介绍
树状数组,顾名思义,就是树状的一维数组。
二叉树同样也可以用一维数组存储。我们以二叉树进行类比。
如图所示,图中节点的序号就是存在数组中的下标。
记父节点序号为 \(p\),子节点序号为 \(s\)。
则有:
\(p\) \(=\) \(s\) \(/\) \(2\) (向下取整)。
左子节点 \(s_{left}\) \(=\) \(p\) \(* 2\) 。
右子节点 \(s_{right}\) \(=\) \(p\) \(*2+1\) 。
综上可知,二叉树能用一维数组存,是由于其父子节点间存在一定关系,以至于不需要用额外的变量来表示信息。
那类比到树状数组中,可以发现:
\(c\)数组即为树状数组。\(c_i\) 表示区间\(a\)\([i-lowbit(i),i]\) 的和。
同样记父节点下标为 \(p\) ,子节点下标为 \(s\)。
则有:
\(p\) \(=\) \(s\) \(+\) \(lowbit(s)\)。
由这条公式亦可反推出:
\(s\) \(=\) \(p\) \(-\) \(2^i\)(\(0 \le i < p_{last}\))
这里的 \(p_{last}\) 指的是 \(p\) 二进制表示下最后一位 \(1\) 所在的位数。
例如:\(6\) 的二进制数表示为 \(110\),则它的 \(p_{last}\) 为 \(1\)。(这里的位数从右往左从\(0\)开始记)。
因为公式 \(1\) 由 \(s\) 加上自身 \(lowbit(s)\) 得到 \(p\) 其过程一定会产生进位。且 \(lowbit(s)\) 一定小于 \(lowbit(p)\) ,所以可以倒推得到子节点。
由于以上关系,树状数组不仅可以用一维数组存。而且还衍生出了一系列用途。
树状数组功能
单点增加
Q:给序列中的一个数 \(a[x]\) 加上 \(y\) 。此时如何维护树状数组?
A:将所有包含 \(a[x]\) 的节点加上 \(y\) 即可,也就是 \(c[x]\) 和它所有的祖先节点。
ps:初始化时亦可运用此操作。
点击查看代码
void add(int x,int y){
for (; x <= N;x += x&-x) c[x] += y;
return ;
}
动态维护前缀和
之所以说动态维护,因为用树状数组维护前缀和只需要 \(\log N\) 的时间复杂度。更为优秀。
Q:求 \(a\) 数组 \(a_i \sim a_x\) 的和。
A:将数 \(x\) 分成若干个区间。
区间共同特点:若区间结尾为 \(R\),则区间长度就等于 \(lowbit(R)\),即 \(R\) 二进制分解下最小的整数次幂。
举例:当 \(x\) = \(7\) 时
如图所示。
区间划分方式与树状数组相同。前面又提到“\(c\)数组即为树状数组。\(c_i\) 表示区间\(a\)\([i-lowbit(i),i]\) 的和。”
因此只需要将这几个区间所对应的 \(c_i\) 相加。即可得到前缀和。
点击查看代码
int ask(int x){
int ans = 0;
for (; x ; x -= x & -x) ans += c[x];
return ans;
}
求逆序对
桶排+树状数组:
1.桶排部分:
对于一个序列 \(a\) , 我们建立一个 \(cnt\) 数组,\(cnt[x]\) 表示 \(x\) 在序列 \(a\) 中出现过的次数。当 \(a_i=val\) 时,\(cnt[val]++\)。
2.树状数组部分:
倒序扫描序列 \(a\),对于新加入的数 \(a_i\),查询 \(cnt[1~a_i-1]\) 的前缀和,并将返回的前缀和加入答案。前缀和部分就可以用树状数组来维护。
操作简单粗暴,但相当好用。
点击查看代码
for ( int i = n; i; i --) {
ans += ask (a[i] - 1);
add (a[i] , 1 );
}
\(-End-\)
\(2023.1.6\)
标签:前缀,树状,int,lowbit,笔记,数组,节点 From: https://www.cnblogs.com/lzyan-blog/p/17030992.html