你干嘛,并查集之后,就到了树形数据结构了,O(∩_∩)O哈哈~

---

河马~~~

• 进入正题

树状数组

树状数组的特点是代码量小,常数小.但具有局限性,如处理区间最大值.

需要知道的是:
普通树状数组维护的信息及运算要满足 结合律 且 可差分，如 加法（和）、乘法（积）、异或等。

• 结合律： $(x\circ y)\circ z=x\circ (y\circ z)$ ，其中 $\circ$ 是一个二元运算符。

• 可差分：具有逆运算的运算，即已知 $x\circ y$ 和 $x$ 可以求出 $y$ 。

在树状数组中,以 $c$ 数组表示树状数组,且每个节点管辖特定的区间,那么在树状数组中, $c_x$ 管理的区间为 $[x-lowbit(x)+1,x]$ , 长度为 $lowbit(x)$.

//lowbit 运算
int lowbit(int x) {
    return x & (-x); // 利用补码性质
}

既然,每个节点有了特定的管辖区域,那么我们就可以解决区间查询的问题了.

区间查询

众所周知,我们可以用 $[1,r]-[1,l-1]$ 得到 $[l,r]$.
于是区间问题就变成了前缀和问题了.

那前缀和问题与该如何求解呢?
设想我们现在要求 $[1,x]$ ,我们是否可以将这一段区间分成几个小区间来求解？是的，我们可以.回顾 $c_x$ 表示的区间 $[x-lowbit(x)+1,x]$ ,既然这段区间可以表示出来,那我们就要求右端点为 $x-lowbit(x)$ 的区间,又因为 $c_{x-lowbit(x)}$ 可以表示区间 $[x-lowbit(x)-lowbit(x-lowbit(x)),x-lowbit(x)]$…以此类推即可覆盖区间 $[1,x]$

具体的,我们有:

• 从 $c[x]$ 开始往前跳，有 $c[x]$ 管辖 $a[x-\mathrm{lowbit}(x)+1\dots x]$ ；
• 令 $x\leftarrow x-\mathrm{lowbit}(x)$ ，如果 $x=0$ 说明已经跳到尽头了，终止循环；否则回到第一步。
• 将跳到的 $c$ 合并(记录答案)。

      int query ( int x ){
        int ans = 0 ;
        for ( ; x ; x -= lowbit ( x ) ){
            ans += c[x] ;
        }
      }

单点修改

等等,你应该还没了解树状数组的树形结构吧(树状也,怎可不见矣?)

那么我们先了解一下树状数组的一些性质吧.
我们记 $l_x$ 表示 $c_x$ 的区间左端点.再者我们知道一个数 $x$ 可以表示为 $s\ast 2^{k+1}+2^k$ , 则 $lowbit(x)=2^k$

• 性质 $1$ :当 $x\le y$ , 有 $c_x$ 与 $c_y$ 不交或包含

证明:设 $y=s\ast 2^{k+1}+2^k,x=s\ast 2^{k+1}+b(b\le 2^k)$ ,那么假设 $c_x$ 与 $c_y$ 相交.那么有 $l_y\le x$ .又因为 $l_x=s\ast 2^{k+1}+b-lowbit(b)+1\ge l_y$ , 故 $l_y\le l_x\le x\le y$ ,证毕.

• 性质 $2$ : $c_x$ 真包含于 $c_{x+lowbit(x)}$

证明:设 $x=s\ast 2^{k+1}+2^k,l_x=s\ast 2^{k+1}+1$,记 $y=x+lowbit(x)$ ,有 $l_y=(s+1)\ast 2^{k+1}-lowbit((s+1)\ast 2^{k+1})+1\le l_x$.证毕.

• 性质 $3$ : 对于 $x<y<x+lowbit(x)$ 有 $c_x$ 与 $c_y$ 不交.

证明:若 $c_x$ 与 $c_y$ 交, 设 $x=s\ast 2^{k+1}+2^k,y=x+b(b<2^k)$ ,则 $l_y\le x$ ,而 $l_y=x+b-lowbit(b)+1>x$,矛盾.证毕.

有了上边的性质,就可以观察树状数组了.(到时可能会放图)

对于单点修改 $a_x$ ,发现只有管辖区间有 $x$ 的 $c$ 数组才会被更新(显然),结合性质 $1$ ,我们发现若 $c_y$ 包含 $x$ ,则一定包含 $c_x$ , 又在形态上 $c_y$ 是 $c_x$ 的祖先,因此我们可以从 $x$ 开始不断跳父亲，直到跳得超过了原数组长度为止。Code:

    void updata ( int x , int val ){
        for ( ; x <= n; x += lowbit(x) ){
            c[x] += val ; 
        }
    }

树状数组 1：单点修改，区间查询

代码

树状数组 2：区间修改，单点查询

提示：差分数组的前缀和 Code

区间加及区间和

该问题可以使用两个树状数组维护差分数组解决。

具体的,设 $d_i=a_i-a_{i-1}$ , 那么 ${\sum }_{i=1}^r{a}_i={\sum }_{i=1}^r{\sum }_{j=1}^i{d}_i$
可以看出 $d_k$ 会出现 $(r-k+1)$ 次,于是乎式子变成了这样:
${\sum }_{i=1}^r{d}_i\ast (r+1)-{\sum }_{i=1}^r{d}_i\ast i$ .
这样我们只需用两个树状数组分别维护 $d_i$ 以及 $d_i\ast i$ 即可.
对于区间加来说, $d_l$ 增加 $val$ , $d_{r+1}$ 减少 $val$ , 而对于第二个树状数组来说,在第 $l$ 节点上增加 $val\ast l$ ,在第 $r+1$ 节点上减少 $val\ast (r+1)$.

LOJ#132. 树状数组 3 ：区间修改，区间查询

代码

二维树状数组

本蒟蒻还未掌握,到时再Update.

权值树状数组

首先先明白一个序列 $a$ 的权值数组是什么

权值数组‌是一个一维数组，其中数组的下标对应原始序列中元素的值，数组元素的值表示原始序列中该下标值出现的次数。

离散化处理‌：当元素值范围较大时，可先离散化原始序列，再构建权值数组以压缩空间.

栗子就不举了.(逃)
而事实上,权值树状数组就是在权值数组上构建树状数组.他可以解决一些经典问题.

单点修改，查询全局第 $k$ 小

可以考虑在权值树状数组上进行二分,每次都要 $O(logN)$ 查询区间和,所以时间复杂度为 $O(lo{g}^{2}N)$ .
时间都去哪了?
由于区间和耗费太多时间,于是聪明的你想的了倍增.具体的:
设 $x=0$ ， $\mathrm{sum}=0$ ，枚举 $i$ 从 $lo{g}_{2}n$ 降为 $0$ ：

• 查询权值数组中 $[x+1\dots x+2^i]$ 的区间和 $t$ 。
• 如果 $\mathrm{sum}+t<k$ ，扩展成功， $x\leftarrow x+2^i$ ， $\mathrm{sum}\leftarrow \mathrm{sum}+t$ ；否则扩展失败，不操作。

这样得到的 $x$ 是满足 $[1\dots x]$ 前缀和 $<k$ 的最大值，所以最终 $x+1$ 就是答案。

看起来这种方法时间效率没有任何改善，但事实上，查询 $[x+1\dots x+2^i]$ 的区间和只需访问 $c[x+2^i]$ 的值即可。

原因很简单，考虑 $\mathrm{lowbit}(x+2^i)$ ，它一定是 $2^i$ ，因为 $x$ 之前只累加过 $2^j$ 满足 $j>i$ 。因此 $c[x+2^i]$ 表示的区间就是 $[x+1\dots x+2^i]$ 。

如此一来，时间复杂度降低为 $\Theta (\log n)$ 。

P1138 第 k 小整数

这道题说实话用树状数组太不实际了,但很有生活可以练练手.

struct TreeArray{
    int c[N] ;
    void updata ( int x , int val ){
        for ( ; x <= 30000 ; x += lowbit( x ) ){
            c[x] += val ;
        }
    }
    int query ( int x ){
        int ans = 0 ;
        for ( ; x ; x -= lowbit(x ) ){
            ans += c[x] ;
        }
        return ans ;
    }
    int ksmall ( int x ){
        int sum = 0 , k = 0 ;
        for ( int i = log2(30000) ; i >= 0 ; --i ){
            k += (1ll << i) ;
            if ( k > 30000 || sum + c[k] >= x ){
                k -= (1ll << i ) ;
            }else sum += c[k] ;
        }
        return k + 1 ;
    }
}t;

记录

全局逆序对

这个需要思考,我们可以从大到小依次将每个数扔进权值树状数组中进行维护,设这个数为 $x$ , 则我们将答案加上 ${\sum }_{i=1}^{x-1}{b}_i$ .($b_i$ 为数 $i$ 出现的次数),正确性很显然.
这里就不写模板了,直接上一道题.

P1966 [NOIP 2013 提高组] 火柴排队

提示:将计算公式展开,再利用排序不等式,可以知道答案就是以 $a_i$ 为第一关键字, $b_i$ 跟随 $a_i$ 排序后的位置的逆序对个数.(可能有点绕).代码.

---

对于本蒟蒻,学到这里是个大概了,还有一些技巧以及高级维护操作本蒟蒻还没有学会,到时应该会Update的.

习题

P3605 [USACO17JAN] Promotion Counting P

我们记答案数组为 $ans$ , 那么 $an{s}_x=$ 比 $x$ 强的下属个数.而当你 $DFS$ 的时候,你会记录之前的信息,不过没有关系, $an{s}_x=进入子树后的信息-之前没有进入子树时的信息$ ,代码/记录.

P1972 [SDOI2009] HH的项链

先将 $l_i,r_i$ 以 $r$ 为第一关键字从小到大排序,我们依次遍历,当碰到一个数 $x$ 时,检查在树状数组中是否维护了 $x$ , 若有则消除之前的维护,并添加新的维护,从而达到目的.(估计还是太抽象了)代码

P4113 [HEOI2012] 采花

跟上一道题十分类似,这里只做些许提示:维护每个元素最后以及倒数第二次出现的位置.
代码.

好像可以把出现两次扩展到出现 $k$ 次来出题.