20190509：学校-3-树状数组

树状数组

---

树状数组的作用：计算一些数据的从1开始计算到$i$位置的和、从1位置到$i$位置的最大值，等。这些运算都必须满足有聚合运算的性质，（满足结合律）。例如，对于求最大值，定义$a(M)b$为求$a$与$b$的最大值，与加法的结合律相同，由结合律存在下式：

$$[a(M)b](M)c=a(M)[b(M)c]$$

树状数组是一种数据结构。对于：

$$a_1,a_2,a_3,...,a_n$$

若将其使用树状数组，则会有$\le \log n$个摊（分组）。

对摊的定义与解释：

举一个简单的例子：将7写成二进制：

$$7=(111{)}_2$$

$$21=(10101{)}_2=1\ast 2^4+1\ast 2^2+1$$

7可分为 （前4）+（中2）+（后1）。现在对于$a_1\dots a_{21}$来说，可以通过同样的编码方法将其分组：

$$a_1+...a_{21}=(a_1+...+a_{16})+(a_{17}+...+a_{20})+(a_{21})$$

$$\begin{gathered} T_1:a_1\to a_1 \\ {T}_2:a_1\to a_2 \\ {T}_3:a_3\to a_3 \\ {T}_4:a_1\to a_4 \\ {T}_5:a_5\to a_5 \\ {T}_6:a_5\to a_6 \\ {T}_7:a_7\to a_7 \\ {T}_8:a_1\to a_8 \end{gathered}$$

例如，对于$a_1,\dots ,a_{64}$而言，：

长度为64的只有一堆：[1, 64]；

长度为32的有2，1堆：[1, 32]​，[33,64]​；

长度为16的有4，2堆：[1, 16]​，[17, 32]，​[33, 48]​，[49, 64]；

长度为8的有8，4堆：[1, 8]，[9, 16]，[17, 24]，[25, 32]，[33, 40]，[41, 48]，[49, 56]，[57, 64]；

……等。

对于末尾重复的区间，删去较小的区间，保留较大的区间，以做到节省的目的。在上面的例子当中，可以发现：区间最末尾的值$0<t_i\le n$，出现且仅出现一次，所以可以发现，总共存在$n$个区间，所以有$\le \log n$个分组

在上面的例子当中，每个摊所管的数量可以得到规律：对于每个$T[i]$，其所管的长度为$lb(i)$

上面的$lb(i)$为“low bit”，为在二进制数当中的最后一个出现的$1$所代表的十进制数，例如：对于12而言，$12=(1100{)}_2$，则最后一个$1$为$(100{)}_2=4$，则$lb(12)=4$。所以$T[12]$所管理的区间为$[9,12]$。

同样地，可以总结出：对于每一个$S[i]$，所管的区间为：$[i-lb(i)+1,i]$。

在树状数组当中，计算的时候，采用上述的摊的计算方式。由此结束了计算的时候的解释。

综合上面的叙述可以不难发现：对于$a_1,a_2,a_3,\dots ,a_n$而言，一共会定义$n$个数组，$T[n]$，但是在运算的时候，会根据实际的需要，选取相关分组的运算，使得时间复杂度为$O(\log n)$。

首先，必需要对数组进行初始化（共有$\le \log n$个分组）：初始化成为目标运算的值，例如加法即为和，求最大值即为各数组的最大值。例如：

for (int i = 1; i <= n; i ++) { cin >> a[i]; add(i, a[i]); }

这就是当新的值被添加进来的情况，这等价于将第$i$号为的值由$0$改为$a_i$，时间复杂度为$\log N$。

---

对数组进行求和的操作

对数组进行修改：$add(i,\Delta )\Rightarrow a_i\to a_i+\Delta$：

研究对数组进行改动，必须研究改动所带来的牵连影响，研究对$a_i$数据的改动，将影响那些区间的运算结果。

再举个简单的例子：若对于数组的第九个元素进行改动，则： $$\begin{gathered} [9,9]\to t[9]\to 9 \\ [9,10]\to t[10]\to 9+lb(9)=10 \\ [9,12]\to t[12]\to 10+lb(10)=12 \\ [1,16]\to t[16]\to 12+lb(12)=16 \end{gathered}$$

在这个例子当中，会发现上述的区间都会影响，归纳为$t_i’=t_i+lb(i)$。

可以写成以下代码：

void add(int i, int d) { while (i <= n) { T[i] += d; i += lb(i); } }

对数组进行查询第$1-j$个元素之和：$sum(j)\Rightarrow a_1+a_2+\dots +a_j$：

再举一个简单的例子：求前23个元素的和： $$\begin{gathered} \text{ans}+=T[23]\to [23,23]\to 23 \\ \text{ans}+=T[22]\to [21,22]\to 23-lb(23)=22 \\ \text{ans}+=T[20]\to [16,20]\to 22-lb(22)=20 \\ \text{ans}+=T[16]\to [1,16]\to 20-lb(20)=16 \\ 16-lb(16)=0 \end{gathered}$$

将上述规律归纳成代码：

int sum(int i) { int ans = 0; while (i > 0) { ans += T[i]; i -= lb(i); } return ans; }

---

对数组进行最大值的操作：

对数组进行修改：$add(i,\Delta )\Rightarrow a_i\to a_i+\Delta \Rightarrow T[m\dots n]=\max \{T[m\dots n],a[i]+\Delta \}$

同理：

void add(int i, int d) { while (i <= n) { T[i] = max(T[i], a[i] + d); i += lb(i); } }

对数组进行计算取最值：$max(j)\Rightarrow \max \{a_1,a_2,a_3,\dots ,a_j\}$

同理：

int max(int i) { int ans = 0; while (i > 0) { ans = max(ans, T[i]); i -= lb(i); } }

---

再论$lb(i)$：

由于$lb(i)$为$i$转换为二进制后的自后向前数到的第一个$1$和若干个$0$的十进制表示，所以便可以将$lb(i)$的计算成$lb(i)=i\&(-i)$。对于$-i$，计算机会对其进行取反加一的操作（负数以其正值得补码形式表达）。例如对于$(011011000{)}_2$取反：$(100100111{)}_2$，再加一得到$(100101000{)}_2$。此时的（位运算）$i$与$-i$的与就是$lb(i)$的值。例子： $$\begin{gathered} (011011000{)}_2 \\ \&(100101000{)}_2 \\ ---------- \\ (000001000{)}_2=8 \end{gathered}$$ 则$lb(216)=lb[(011011000{)}_2]=8$ int lb(int i) { return i & (-i); }

正因为这个特性：可以将某一个二进制数表达为：$\dots 10\dots 0(n\text{ zeros})$。

则其的相反数即为：$\dots 01\dots 1(n\text{ ones})+1=\dots 10\dots 0(n\text{ zeros})$。将两数取与，则在第$1-n$为皆为$0\&1=0$，在第$n+1$位为$1\&1=1$，其后也皆为$0$。（此处的位数顺序为自后向前）

综上所述，可以发现：使用树状数组，无论是添加元素，修改元素，还是查询某位置的结果，其事件复杂度均相同，为$\log n$。