跳转至

樹狀數組

引入

樹狀數組是一種支持 單點修改 和 區間查詢 的，代碼量小的數據結構。

什麼是「單點修改」和「區間查詢」？

假設有這樣一道題：

已知一個數列 \(a\)，你需要進行下面兩種操作：

  • 給定 \(x, y\)，將 \(a[x]\) 自增 \(y\)。
  • 給定 \(l, r\)，求解 \(a[l \ldots r]\) 的和。

其中第一種操作就是「單點修改」，第二種操作就是「區間查詢」。

類似地，還有：「區間修改」、「單點查詢」。它們分別的一個例子如下：

  • 區間修改：給定 \(l, r, x\)，將 \(a[l \ldots r]\) 中的每個數都分別自增 \(x\)；
  • 單點查詢：給定 \(x\)，求解 \(a[x]\) 的值。

注意到，區間問題一般嚴格強於單點問題，因為對單點的操作相當於對一個長度為 \(1\) 的區間操作。

普通樹狀數組維護的信息及運算要滿足 結合律 且 可差分，如加法（和）、乘法（積）、異或等。

  • 結合律：\((x \circ y) \circ z = x \circ (y \circ z)\)，其中 \(\circ\) 是一個二元運算符。
  • 可差分：具有逆運算的運算，即已知 \(x \circ y\) 和 \(x\) 可以求出 \(y\)。

需要注意的是：

  • 模意義下的乘法若要可差分，需保證每個數都存在逆元（模數為質數時一定存在）；
  • 例如 \(\gcd\)，\(\max\) 這些信息不可差分，所以不能用普通樹狀數組處理，但是：

事實上，樹狀數組能解決的問題是線段樹能解決的問題的子集：樹狀數組能做的，線段樹一定能做；線段樹能做的，樹狀數組不一定可以。然而，樹狀數組的代碼要遠比線段樹短，時間效率常數也更小，因此仍有學習價值。

有時，在差分數組和輔助數組的幫助下，樹狀數組還可解決更強的 區間加單點值 和 區間加區間和 問題。

樹狀數組

初步感受

先來舉個例子：我們想知道 \(a[1 \ldots 7]\) 的前綴和，怎麼做？

一種做法是：\(a_1 + a_2 + a_3 + a_4 + a_5 + a_6 + a_7\)，需要求 \(7\) 個數的和。

但是如果已知三個數 \(A\)，\(B\)，\(C\)，\(A = a[1 \ldots 4]\) 的和，\(B = a[5 \ldots 6]\) 的總和，\(C = a[7 \ldots 7]\) 的總和（其實就是 \(a[7]\) 自己）。你會怎麼算？你一定會回答：\(A + B + C\)，只需要求 \(3\) 個數的和。

這就是樹狀數組能快速求解信息的原因：我們總能將一段前綴 \([1, n]\) 拆成 不多於 \(\boldsymbol{\log n}\) 段區間，使得這 \(\log n\) 段區間的信息是 已知的。

於是，我們只需合併這 \(\log n\) 段區間的信息，就可以得到答案。相比於原來直接合並 \(n\) 個信息，效率有了很大的提高。

不難發現信息必須滿足結合律，否則就不能像上面這樣合併了。

下面這張圖展示了樹狀數組的工作原理：

最下面的八個方塊代表原始數據數組 \(a\)。上面參差不齊的方塊（與最上面的八個方塊是同一個數組）代表數組 \(a\) 的上級——\(c\) 數組。

\(c\) 數組就是用來儲存原始數組 \(a\) 某段區間的和的，也就是説，這些區間的信息是已知的，我們的目標就是把查詢前綴拆成這些小區間。

例如，從圖中可以看出：

  • \(c_2\) 管轄的是 \(a[1 \ldots 2]\)；
  • \(c_4\) 管轄的是 \(a[1 \ldots 4]\)；
  • \(c_6\) 管轄的是 \(a[5 \ldots 6]\)；
  • \(c_8\) 管轄的是 \(a[1 \ldots 8]\)；
  • 剩下的 \(c[x]\) 管轄的都是 \(a[x]\) 自己（可以看做 \(a[x \ldots x]\) 的長度為 \(1\) 的小區間）。

不難發現，\(c[x]\) 管轄的一定是一段右邊界是 \(x\) 的區間總信息。我們先不關心左邊界，先來感受一下樹狀數組是如何查詢的。

舉例：計算 \(a[1 \ldots 7]\) 的和。

過程：從 \(c_{7}\) 開始往前跳，發現 \(c_{7}\) 只管轄 \(a_{7}\) 這個元素；然後找 \(c_{6}\)，發現 \(c_{6}\) 管轄的是 \(a[5 \ldots 6]\)，然後跳到 \(c_{4}\)，發現 \(c_{4}\) 管轄的是 \(a[1 \ldots 4]\) 這些元素，然後再試圖跳到 \(c_0\)，但事實上 \(c_0\) 不存在，不跳了。

我們剛剛找到的 \(c\) 是 \(c_7, c_6, c_4\)，事實上這就是 \(a[1 \ldots 7]\) 拆分出的三個小區間，合併得到答案是 \(c_7 + c_6 + c_4\)。

舉例：計算 \(a[4 \ldots 7]\) 的和。

我們還是從 \(c_7\) 開始跳，跳到 \(c_6\) 再跳到 \(c_4\)。此時我們發現它管理了 \(a[1 \ldots 4]\) 的和，但是我們不想要 \(a[1 \ldots 3]\) 這一部分，怎麼辦呢？很簡單，減去 \(a[1 \ldots 3]\) 的和就行了。

那不妨考慮最開始，就將查詢 \(a[4 \ldots 7]\) 的和轉化為查詢 \(a[1 \ldots 7]\) 的和，以及查詢 \(a[1 \ldots 3]\) 的和，最終將兩個結果作差。

管轄區間

那麼問題來了，\(c[x](x \ge 1)\) 管轄的區間到底往左延伸多少？也就是説，區間長度是多少？

樹狀數組中，規定 \(c[x]\) 管轄的區間長度為 \(2^{k}\)，其中：

  • 設二進制最低位為第 \(0\) 位，則 \(k\) 恰好為 \(x\) 二進制表示中，最低位的 1 所在的二進制位數；
  • \(2^k\)（\(c[x]\) 的管轄區間長度）恰好為 \(x\) 二進制表示中，最低位的 1 以及後面所有 0 組成的數。

舉個例子，\(c_{88}\) 管轄的是哪個區間？

因為 \(88_{(10)}=01011000_{(2)}\)，其二進制最低位的 1 以及後面的 0 組成的二進制是 1000，即 \(8\)，所以 \(c_{88}\) 管轄 \(8\) 個 \(a\) 數組中的元素。

因此，\(c_{88}\) 代表 \(a[81 \ldots 88]\) 的區間信息。

我們記 \(x\) 二進制最低位 1 以及後面的 0 組成的數為 \(\operatorname{lowbit}(x)\)，那麼 \(c[x]\) 管轄的區間就是 \([x-\operatorname{lowbit}(x)+1, x]\)。

這裏注意：\(\boldsymbol{\operatorname{lowbit}}\) 指的不是最低位 1 所在的位數 \(\boldsymbol{k}\)，而是這個 1 和後面所有 0 組成的 \(\boldsymbol{2^k}\)。

怎麼計算 lowbit？根據位運算知識，可以得到 lowbit(x) = x & -x。

lowbit 的原理

將 x 的二進制所有位全部取反，再加 1，就可以得到 -x 的二進制編碼。例如，\(6\) 的二進制編碼是 110，全部取反後得到 001，加 1 得到 010。

設原先 x 的二進制編碼是 (...)10...00，全部取反後得到 [...]01...11，加 1 後得到 [...]10...00，也就是 -x 的二進制編碼了。這裏 x 二進制表示中第一個 1 是 x 最低位的 1。

(...) 和 [...] 中省略號的每一位分別相反，所以 x & -x = (...)10...00 & [...]10...00 = 10...00，得到的結果就是 lowbit。

實現 
1
2
3
4
5
6
7
8
int lowbit(int x) {
  // x 的二進制中，最低位的 1 以及後面所有 0 組成的數。
  // lowbit(0b01011000) == 0b00001000
  //          ~~~~^~~~
  // lowbit(0b01110010) == 0b00000010
  //          ~~~~~~^~
  return x & -x;
}

1
2
3
4
5
6
7
8
9
def lowbit(x):
    """
    x 的二進制中，最低位的 1 以及後面所有 0 組成的數。
    lowbit(0b01011000) == 0b00001000
            ~~~~~^~~
    lowbit(0b01110010) == 0b00000010
            ~~~~~~~^~
    """
    return x & -x

區間查詢

接下來我們來看樹狀數組具體的操作實現，先來看區間查詢。

回顧查詢 \(a[4 \ldots 7]\) 的過程，我們是將它轉化為兩個子過程：查詢 \(a[1 \ldots 7]\) 和查詢 \(a[1 \ldots 3]\) 的和，最終作差。

其實任何一個區間查詢都可以這麼做：查詢 \(a[l \ldots r]\) 的和，就是 \(a[1 \ldots r]\) 的和減去 \(a[1 \ldots l - 1]\) 的和，從而把區間問題轉化為前綴問題，更方便處理。

事實上，將有關 \(l \ldots r\) 的區間詢問轉化為 \(1 \ldots r\) 和 \(1 \ldots l - 1\) 的前綴詢問再差分，在競賽中是一個非常常用的技巧。

那前綴查詢怎麼做呢？回顧下查詢 \(a[1 \ldots 7]\) 的過程：

從 \(c_{7}\) 往前跳，發現 \(c_{7}\) 只管轄 \(a_{7}\) 這個元素；然後找 \(c_{6}\)，發現 \(c_{6}\) 管轄的是 \(a[5 \ldots 6]\)，然後跳到 \(c_{4}\)，發現 \(c_{4}\) 管轄的是 \(a[1 \ldots 4]\) 這些元素，然後再試圖跳到 \(c_0\)，但事實上 \(c_0\) 不存在，不跳了。

我們剛剛找到的 \(c\) 是 \(c_7, c_6, c_4\)，事實上這就是 \(a[1 \ldots 7]\) 拆分出的三個小區間，合併一下，答案是 \(c_7 + c_6 + c_4\)。

觀察上面的過程，每次往前跳，一定是跳到現區間的左端點的左一位，作為新區間的右端點，這樣才能將前綴不重不漏地拆分。比如現在 \(c_6\) 管的是 \(a[5 \ldots 6]\)，下一次就跳到 \(5 - 1 = 4\)，即訪問 \(c_4\)。

我們可以寫出查詢 \(a[1 \ldots x]\) 的過程：

  • 從 \(c[x]\) 開始往前跳，有 \(c[x]\) 管轄 \(a[x-\operatorname{lowbit}(x)+1 \ldots x]\)；
  • 令 \(x \gets x - \operatorname{lowbit}(x)\)，如果 \(x = 0\) 説明已經跳到盡頭了，終止循環；否則回到第一步。
  • 將跳到的 \(c\) 合併。

實現時，我們不一定要先把 \(c\) 都跳出來然後一起合併，可以邊跳邊合併。

比如我們要維護的信息是和，直接令初始 \(\mathrm{ans} = 0\)，然後每跳到一個 \(c[x]\) 就 \(\mathrm{ans} \gets \mathrm{ans} + c[x]\)，最終 \(\mathrm{ans}\) 就是所有合併的結果。

實現 
1
2
3
4
5
6
7
8
int getsum(int x) {  // a[1]..a[x]的和
  int ans = 0;
  while (x > 0) {
    ans = ans + c[x];
    x = x - lowbit(x);
  }
  return ans;
}

1
2
3
4
5
6
def getsum(x): # a[1]..a[x]的和
    ans = 0
    while x > 0:
        ans = ans + c[x]
        x = x - lowbit(x)
    return ans

樹狀數組與其樹形態的性質

在講解單點修改之前，先講解樹狀數組的一些基本性質，以及其樹形態來源，這有助於更好理解樹狀數組的單點修改。

我們約定：

  • \(l(x) = x - \operatorname{lowbit}(x) + 1\)。即，\(l(x)\) 是 \(c[x]\) 管轄範圍的左端點。
  • 對於任意正整數 \(x\)，總能將 \(x\) 表示成 \(s \times 2^{k + 1} + 2^k\) 的形式，其中 \(\operatorname{lowbit}(x) = 2^k\)。
  • 下面「\(c[x]\) 和 \(c[y]\) 不交」指 \(c[x]\) 的管轄範圍和 \(c[y]\) 的管轄範圍不相交，即 \([l(x), x]\) 和 \([l(y), y]\) 不相交。「\(c[x]\) 包含於 \(c[y]\)」等表述同理。

性質 \(\boldsymbol{1}\)：對於 \(\boldsymbol{x \le y}\)，要麼有 \(\boldsymbol{c[x]}\) 和 \(\boldsymbol{c[y]}\) 不交，要麼有 \(\boldsymbol{c[x]}\) 包含於 \(\boldsymbol{c[y]}\)。

證明

證明：假設 \(c[x]\) 和 \(c[y]\) 相交，即 \([l(x), x]\) 和 \([l(y), y]\) 相交，則一定有 \(l(y) \le x \le y\)。

將 \(y\) 表示為 \(s \times 2^{k +1} + 2^k\)，則 \(l(y) = s \times 2^{k + 1} + 1\)。所以，\(x\) 可以表示為 \(s \times 2^{k +1} + b\)，其中 \(1 \le b \le 2^k\)。

不難發現 \(\operatorname{lowbit}(x) = \operatorname{lowbit}(b)\)。又因為 \(b - \operatorname{lowbit}(b) \ge 0\)，

所以 \(l(x) = x - \operatorname{lowbit}(x) + 1 = s \times 2^{k +1} + b - \operatorname{lowbit}(b) +1 \ge s \times 2^{k +1} + 1 = l(y)\)，即 \(l(y) \le l(x) \le x \le y\)。

所以，如果 \(c[x]\) 和 \(c[y]\) 相交，那麼 \(c[x]\) 的管轄範圍一定完全包含於 \(c[y]\)。

性質 \(\boldsymbol{2}\)：在 \(\boldsymbol{c[x]}\) 真包含於 \(\boldsymbol{c[x + \operatorname{lowbit}(x)]}\)。

證明

證明：設 \(y = x + \operatorname{lowbit}(x)\)，\(x = s \times 2^{k + 1} + 2^k\)，則 \(y = (s + 1) \times 2^{k +1}\)，\(l(x) = s \times 2^{k + 1} + 1\)。

不難發現 \(\operatorname{lowbit}(y) \ge 2^{k + 1}\)，所以 \(l(y) = (s + 1) \times 2^{k + 1} - \operatorname{lowbit}(y) + 1 \le s \times 2^{k +1} + 1= l(x)\)，即 \(l(y) \le l(x) \le x < y\)。

所以，\(c[x]\) 真包含於 \(c[x + \operatorname{lowbit}(x)]\)。

性質 \(3\)：對於任意 \(\boldsymbol{x < y < x + \operatorname{lowbit}(x)}\)，有 \(\boldsymbol{c[x]}\) 和 \(\boldsymbol{c[y]}\) 不交。

證明

證明：設 \(x = s \times 2^{k + 1} + 2^k\)，則 \(y = x + b = s \times 2^{k + 1} + 2^k + b\)，其中 \(1 \le b < 2^k\)。

不難發現 \(\operatorname{lowbit}(y) = \operatorname{lowbit}(b)\)。又因為 \(b - \operatorname{lowbit}(b) \ge 0\)，

因此 \(l(y) = y - \operatorname{lowbit}(y) + 1 = x + b - \operatorname{lowbit}(b) + 1 > x\)，即 \(l(x) \le x < l(y) \le y\)。

所以，\(c[x]\) 和 \(c[y]\) 不交。

有了這三條性質的鋪墊，我們接下來看樹狀數組的樹形態（請忽略 \(a\) 向 \(c\) 的連邊）。

事實上，樹狀數組的樹形態是 \(x\) 向 \(x + \operatorname{lowbit}(x)\) 連邊得到的圖，其中 \(x + \operatorname{lowbit}(x)\) 是 \(x\) 的父親。

注意，在考慮樹狀數組的樹形態時，我們不考慮樹狀數組大小的影響，即我們認為這是一棵無限大的樹，方便分析。實際實現時，我們只需用到 \(x \le n\) 的 \(c[x]\)，其中 \(n\) 是原數組長度。

這棵樹天然滿足了很多美好性質，下面列舉若干（設 \(fa[u]\) 表示 \(u\) 的直系父親）：

  • \(u < fa[u]\)。
  • \(u\) 大於任何一個 \(u\) 的後代，小於任何一個 \(u\) 的祖先。
  • 點 \(u\) 的 \(\operatorname{lowbit}\) 嚴格小於 \(fa[u]\) 的 \(\operatorname{lowbit}\)。
證明

設 \(y = x + \operatorname{lowbit}(x)\)，\(x = s \times 2^{k + 1} + 2^k\)，則 \(y = (s + 1) \times 2^{k +1}\)，不難發現 \(\operatorname{lowbit}(y) \ge 2^{k + 1} > \operatorname{lowbit}(x)\)，證畢。

  • 點 \(x\) 的高度是 \(\log_2\operatorname{lowbit}(x)\)，即 \(x\) 二進制最低位 1 的位數。
高度的定義

點 \(x\) 的高度 \(h(x)\) 滿足：如果 \(x \bmod 2 = 1\)，則 \(h(x) = 0\)，否則 \(h(x) = \max(h(y)) + 1\)，其中 \(y\) 代表 \(x\) 的所有兒子（此時 \(x\) 至少存在一個兒子 \(x - 1\)）。

也就是説，一個點的高度恰好比它最高的那個兒子再高 \(1\)。如果一個點沒有兒子，它的高度是 \(0\)。

這裏引出高度這一概念，是為後面解釋複雜度更方便。

  • \(c[u]\) 真包含於 \(c[fa[u]]\)（性質 \(2\)）。
  • \(c[u]\) 真包含於 \(c[v]\)，其中 \(v\) 是 \(u\) 的任一祖先（在上一條性質上歸納）。
  • \(c[u]\) 真包含 \(c[v]\)，其中 \(v\) 是 \(u\) 的任一後代（上面那條性質 \(u\)，\(v\) 顛倒）。
  • 對於任意 \(v' > u\)，若 \(v'\) 不是 \(u\) 的祖先，則 \(c[u]\) 和 \(c[v']\) 不交。
證明

\(u\) 和 \(u\) 的祖先中，一定存在一個點 \(v\) 使得 \(v < v' < fa[v]\)，根據性質 \(3\) 得 \(c[v']\) 不相交於 \(c[v]\)，而 \(c[v]\) 包含 \(c[u]\)，因此 \(c[v']\) 不交於 \(c[u]\)。

  • 對於任意 \(v < u\)，如果 \(v\) 不在 \(u\) 的子樹上，則 \(c[u]\) 和 \(c[v]\) 不交（上面那條性質 \(u\)，\(v'\) 顛倒）。
  • 對於任意 \(v > u\)，當且僅當 \(v\) 是 \(u\) 的祖先，\(c[u]\) 真包含於 \(c[v]\)（上面幾條性質的總結）。這就是樹狀數組單點修改的核心原理。
  • 設 \(u = s \times 2^{k + 1} + 2^k\)，則其兒子數量為 \(k = \log_2\operatorname{lowbit}(u)\)，編號分別為 \(u - 2^t(0 \le t < k)\)。
    • 舉例：假設 \(k = 3\)，\(u\) 的二進制編號為 ...1000，則 \(u\) 有三個兒子，二進制編號分別為 ...0111、...0110、...0100。
證明

在一個數 \(x\) 的基礎上減去 \(2^t\)，\(x\) 二進制第 \(t\) 位會反轉，而更低的位保持不變。

考慮 \(u\) 的兒子 \(v\)，有 \(v + \operatorname{lowbit}(v) = u\)，即 \(v = u - 2^t\) 且 \(\operatorname{lowbit}(v) = 2^t\)。設 \(u = s \times 2^{k + 1} + 2^k\)。

考慮 \(\boldsymbol{0 \le t < k}\)，\(u\) 的第 \(t\) 位及後方均為 \(0\)，所以 \(v = u - 2^t\) 的第 \(t\) 位變為 \(1\)，後面仍為 \(0\)，滿足 \(\operatorname{lowbit}(v) = 2^t\)。

考慮 \(\boldsymbol{t = k}\)，則 \(v = u - 2^k\)，\(v\) 的第 \(k\) 位變為 \(0\)，不滿足 \(\operatorname{lowbit}(v) = 2^t\)。

考慮 \(\boldsymbol{t > k}\)，則 \(v = u - 2^t\)，\(v\) 的第 \(k\) 位是 \(1\)，所以 \(\operatorname{lowbit}(v) = 2^k\)，不滿足 \(\operatorname{lowbit}(v) = 2^t\)。

  • \(u\) 的所有兒子對應 \(c\) 的管轄區間恰好拼接成 \([l(u), u - 1]\)。
    • 舉例：假設 \(k = 3\)，\(u\) 的二進制編號為 ...1000，則 \(u\) 有三個兒子，二進制編號分別為 ...0111、...0110、...0100。
    • c[...0100] 表示 a[...0001 ~ ...0100]。
    • c[...0110] 表示 a[...0101 ~ ...0110]。
    • c[...0111] 表示 a[...0111 ~ ...0111]。
    • 不難發現上面是三個管轄區間的並集恰好是 a[...0001 ~ ...0111]，即 \([l(u), u - 1]\)。
證明

\(u\) 的兒子總能表示成 \(u - 2^t(0 \le t < k)\)，不難發現，\(t\) 越小，\(u - 2^t\) 越大，代表的區間越靠右。我們設 \(f(t) = u - 2^t\)，則 \(f(k - 1), f(k - 2), \ldots, f(0)\) 分別構成 \(u\) 從左到右的兒子。

不難發現 \(\operatorname{lowbit}(f(t)) = 2^t\)，所以 \(l(f(t)) = u - 2^t - 2^t + 1 = u - 2^{t + 1} + 1\)。

考慮相鄰的兩個兒子 \(f(t + 1)\) 和 \(f(t)\)。前者管轄區間的右端點是 \(f(t + 1) = u - 2^{t + 1}\)，後者管轄區間的左端點是 \(l(f(t)) = u - 2^{t + 1} + 1\)，恰好相接。

考慮最左面的兒子 \(f(k - 1)\)，其管轄左邊界 \(l(f(k - 1)) = u - 2^k + 1\) 恰為 \(l(u)\)。

考慮最右面的兒子 \(f(0)\)，其管轄右邊界就是 \(u - 1\)。

因此，這些兒子的管轄區間可以恰好拼成 \([l(u), u - 1]\)。

單點修改

現在來考慮如何單點修改 \(a[x]\)。

我們的目標是快速正確地維護 \(c\) 數組。為保證效率，我們只需遍歷並修改管轄了 \(a[x]\) 的所有 \(c[y]\)，因為其他的 \(c\) 顯然沒有發生變化。

管轄 \(a[x]\) 的 \(c[y]\) 一定包含 \(c[x]\)（根據性質 \(1\)），所以 \(y\) 在樹狀數組樹形態上是 \(x\) 的祖先。因此我們從 \(x\) 開始不斷跳父親，直到跳得超過了原數組長度為止。

設 \(n\) 表示 \(a\) 的大小，不難寫出單點修改 \(a[x]\) 的過程：

  • 初始令 \(x' = x\)。
  • 修改 \(c[x']\)。
  • 令 \(x' \gets x' + \operatorname{lowbit}(x')\)，如果 \(x' > n\) 説明已經跳到盡頭了，終止循環；否則回到第二步。

區間信息和單點修改的種類，共同決定 \(c[x']\) 的修改方式。下面給幾個例子：

  • 若 \(c[x']\) 維護區間和，修改種類是將 \(a[x]\) 加上 \(p\)，則修改方式則是將所有 \(c[x']\) 也加上 \(p\)。
  • 若 \(c[x']\) 維護區間積，修改種類是將 \(a[x]\) 乘上 \(p\)，則修改方式則是將所有 \(c[x']\) 也乘上 \(p\)。

然而，單點修改的自由性使得修改的種類和維護的信息不一定是同種運算，比如，若 \(c[x']\) 維護區間和，修改種類是將 \(a[x]\) 賦值為 \(p\)，可以考慮轉化為將 \(a[x]\) 加上 \(p - a[x]\)。如果是將 \(a[x]\) 乘上 \(p\)，就考慮轉化為 \(a[x]\) 加上 \(a[x] \times p - a[x]\)。

下面以維護區間和，單點加為例給出實現。

實現 
1
2
3
4
5
6
void add(int x, int k) {
  while (x <= n) {  // 不能越界
    c[x] = c[x] + k;
    x = x + lowbit(x);
  }
}

1
2
3
4
def add(x, k):
    while x <= n: # 不能越界
        c[x] = c[x] + k
        x = x + lowbit(x)

建樹

也就是根據最開始給出的序列，將樹狀數組建出來（\(c\) 全部預處理好）。

一般可以直接轉化為 \(n\) 次單點修改，時間複雜度 \(\Theta(n \log n)\)（複雜度分析在後面）。

比如給定序列 \(a = (5, 1, 4)\) 要求建樹，直接看作對 \(a[1]\) 單點加 \(5\)，對 \(a[2]\) 單點加 \(1\)，對 \(a[3]\) 單點加 \(4\) 即可。

也有 \(\Theta(n)\) 的建樹方法，見本頁面 \(\Theta(n)\) 建樹 一節。

複雜度分析

空間複雜度顯然 \(\Theta(n)\)。

時間複雜度：

  • 對於區間查詢操作：整個 \(x \gets x - \operatorname{lowbit}(x)\) 的迭代過程，可看做將 \(x\) 二進制中的所有 \(1\)，從低位到高位逐漸改成 \(0\) 的過程，拆分出的區間數等於 \(x\) 二進制中 \(1\) 的數量（即 \(\operatorname{popcount}(x)\)）。因此，單次查詢時間複雜度是 \(\Theta(\log n)\)；
  • 對於單點修改操作：跳父親時，訪問到的高度一直嚴格增加，且始終有 \(x \le n\)。由於點 \(x\) 的高度是 \(\log_2\operatorname{lowbit}(x)\)，所以跳到的高度不會超過 \(\log_2n\)，所以訪問到的 \(c\) 的數量是 \(\log n\) 級別。因此，單次單點修改複雜度是 \(\Theta(\log n)\)。

區間加區間和

前置知識：前綴和 & 差分。

該問題可以使用兩個樹狀數組維護差分數組解決。

考慮序列 \(a\) 的差分數組 \(d\)，其中 \(d[i] = a[i] - a[i - 1]\)。由於差分數組的前綴和就是原數組，所以 \(a_i=\sum_{j=1}^i d_j\)。

一樣地，我們考慮將查詢區間和通過差分轉化為查詢前綴和。那麼考慮查詢 \(a[1 \ldots r]\) 的和，即 \(\sum_{i=1}^{r} a_i\)，進行推導：

\[ \begin{aligned} &\sum_{i=1}^{r} a_i\\=&\sum_{i=1}^r\sum_{j=1}^i d_j \end{aligned} \]

觀察這個式子，不難發現每個 \(d_j\) 總共被加了 \(r - j + 1\) 次。接着推導：

\[ \begin{aligned} &\sum_{i=1}^r\sum_{j=1}^i d_j\\=&\sum_{i=1}^r d_i\times(r-i+1) \\=&\sum_{i=1}^r d_i\times (r+1)-\sum_{i=1}^r d_i\times i \end{aligned} \]

\(\sum_{i=1}^r d_i\) 並不能推出 \(\sum_{i=1}^r d_i \times i\) 的值，所以要用兩個樹狀數組分別維護 \(d_i\) 和 \(d_i \times i\) 的和信息。

那麼怎麼做區間加呢？考慮給原數組 \(a[l \ldots r]\) 區間加 \(x\) 給 \(d\) 帶來的影響。

因為差分是 \(d[i] = a[i] - a[i - 1]\)，

  • \(a[l]\) 多了 \(v\) 而 \(a[l - 1]\) 不變，所以 \(d[l]\) 的值多了 \(v\)。
  • \(a[r + 1]\) 不變而 \(a[r]\) 多了 \(v\)，所以 \(d[r + 1]\) 的值少了 \(v\)。
  • 對於不等於 \(l\) 且不等於 \(r+1\) 的任意 \(i\)，\(a[i]\) 和 \(a[i - 1]\) 要麼都沒發生變化，要麼都加了 \(v\)，\(a[i] + v - (a[i - 1] + v)\) 還是 \(a[i] - a[i - 1]\)，所以其它的 \(d[i]\) 均不變。

那就不難想到維護方式了：對於維護 \(d_i\) 的樹狀數組，對 \(l\) 單點加 \(v\)，\(r + 1\) 單點加 \(-v\)；對於維護 \(d_i \times i\) 的樹狀數組，對 \(l\) 單點加 \(v \times l\)，\(r + 1\) 單點加 \(-v \times (r + 1)\)。

而更弱的問題，「區間加求單點值」，只需用樹狀數組維護一個差分數組 \(d_i\)。詢問 \(a[x]\) 的單點值，直接求 \(d[1 \ldots x]\) 的和即可。

這裏直接給出「區間加區間和」的代碼：

實現 
 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
int t1[MAXN], t2[MAXN], n;

int lowbit(int x) { return x & (-x); }

void add(int k, int v) {
  int v1 = k * v;
  while (k <= n) {
    t1[k] += v, t2[k] += v1;
    // 注意不能寫成 t2[k] += k * v，因為 k 的值已經不是原數組的下標了
    k += lowbit(k);
  }
}

int getsum(int *t, int k) {
  int ret = 0;
  while (k) {
    ret += t[k];
    k -= lowbit(k);
  }
  return ret;
}

void add1(int l, int r, int v) {
  add(l, v), add(r + 1, -v);  // 將區間加差分為兩個前綴加
}

long long getsum1(int l, int r) {
  return (r + 1ll) * getsum(t1, r) - 1ll * l * getsum(t1, l - 1) -
         (getsum(t2, r) - getsum(t2, l - 1));
}

 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
t1 = [0] * MAXN, t2 = [0] * MAXN; n = 0

def lowbit(x):
    return x & (-x)

def add(k, v):
    v1 = k * v
    while k <= n:
        t1[k] = t1[k] + v; t2[k] = t2[k] + v1
        k = k + lowbit(k)

def getsum(t, k):
    ret = 0
    while k:
        ret = ret + t[k]
        k = k - lowbit(k)
    return ret

def add1(l, r, v):
    add(l, v)
    add(r + 1, -v)

def getsum1(l, r):
    return (r) * getsum(t1, r) - l * getsum(t1, l - 1) - \
          (getsum(t2, r) - getsum(t2, l - 1))

根據這個原理，應該可以實現「區間乘區間積」，「區間異或一個數，求區間異或值」等，只要滿足維護的信息和區間操作是同種運算即可，感興趣的讀者可以自己嘗試。

二維樹狀數組

單點修改，子矩陣查詢

二維樹狀數組，也被稱作樹狀數組套樹狀數組，用來維護二維數組上的單點修改和前綴信息問題。

與一維樹狀數組類似，我們用 \(c(x, y)\) 表示 \(a(x - \operatorname{lowbit}(x) + 1, y - \operatorname{lowbit}(y) + 1) \ldots a(x, y)\) 的矩陣總信息，即一個以 \(a(x, y)\) 為右下角，高 \(\operatorname{lowbit}(x)\)，寬 \(\operatorname{lowbit}(y)\) 的矩陣的總信息。

對於單點修改，設：

\[ f(x, i) = \begin{cases}x &i = 0\\f(x, i - 1) + \operatorname{lowbit}(f(x, i - 1)) & i > 0\\\end{cases} \]

即 \(f(x, i)\) 為 \(x\) 在樹狀數組樹形態上的第 \(i\) 級祖先（第 \(0\) 級祖先是自己）。

則只有 \(c(f(x, i), f(y, j))\) 中的元素管轄 \(a(x, y)\)，修改 \(a(x, y)\) 時只需修改所有 \(c(f(x, i), f(y, j))\)，其中 \(f(x, i) \le n\)，\(f(y, j) \le m\)。

正確性證明

\(c(p, q)\) 管轄 \(a(x, y)\)，求 \(p\) 和 \(q\) 的取值範圍。

考慮一個大小為 \(n\) 的一維樹狀數組 \(c_1\)（對應原數組 \(a_1\)）和一個大小為 \(m\) 的一維樹狀數組 \(c_2\)（對應原數組 \(a_2\)）。

則命題等價為：\(c_1(p)\) 管轄 \(a_1[x]\) 且 \(c_2(q)\) 管轄 \(a_2[y]\) 的條件。

也就是説，在樹狀數組樹形態上，\(p\) 是 \(x\) 及其祖先中的一個點，\(q\) 是 \(y\) 及其祖先中的一個點。

所以 \(p = f(x, i)\)，\(q = f(y, j)\)。

對於查詢，我們設：

\[ g(x, i) = \begin{cases}x &i = 0\\g(x, i - 1) - \operatorname{lowbit}(g(x, i - 1)) & i, g(x, i - 1) > 0\\0&\text{otherwise.}\end{cases} \]

則合併所有 \(c(g(x, i), g(y, j))\)，其中 \(g(x, i), g(y, j) > 0\)。

正確性證明

設 \(\circ\) 表示合併兩個信息的運算符（比如，如果信息是區間和，則 \(\circ = +\)）。

考慮一個一維樹狀數組 \(c_1\)，\(c_1[g(x, 0)] \circ c_1[g(x, 1)] \circ c_1[g(x, 2)] \circ \cdots\) 恰好表示原數組上 \([1 \ldots x]\) 這段區間信息。

類似地，設 \(t(x) = c(x, g(y, 0)) \circ c(x, g(y, 1)) \circ c(x, g(y, 2)) \circ \cdots\)，則 \(t(x)\) 恰好表示 \(a(x - \operatorname{lowbit}(x) + 1, 1) \ldots a(x, y)\) 這個矩陣信息。

又類似地，就有 \(t(g(x, 0)) \circ t(g(x, 1)) \circ t(g(x, 2)) \circ \cdots\) 表示 \(a(1, 1) \ldots a(x, y)\) 這個矩陣信息。

其實這裏 \(t(x)\) 這個函數如果看成一個樹狀數組，相當於一個樹狀數組套了一個樹狀數組，這也就是「樹狀數組套樹狀數組」這個名字的來源。

下面給出單點加、查詢子矩陣和的代碼。

實現 
1
2
3
4
5
6
7
8
void add(int x, int y, int v) {
  for (int i = x; i <= n; i += lowbit(i)) {
    for (int j = y; j <= m; j += lowbit(j)) {
      // 注意這裏必須得建循環變量，不能像一維數組一樣直接 while (x <= n) 了
      c[i][j] += v;
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int sum(int x, int y) {
  int res = 0;
  for (int i = x; i > 0; i -= lowbit(i)) {
    for (int j = y; j > 0; j -= lowbit(j)) {
      res += c[i][j];
    }
  }
  return res;
}

int ask(int x1, int y1, int x2, int y2) {
  // 查詢子矩陣和
  return sum(x2, y2) - sum(x2, y1 - 1) - sum(x1 - 1, y2) + sum(x1 - 1, y1 - 1);
}

子矩陣加，求子矩陣和

前置知識：前綴和 & 差分 和本頁面 區間加區間和 一節。

和一維樹狀數組的「區間加區間和」問題類似，考慮維護差分數組。

二維數組上的差分數組是這樣的：

\[ d(i, j) = a(i, j) - a(i - 1, j) - a(i, j - 1) + a(i - 1, j - 1)。 \]
為什麼這麼定義？

這是因為，理想規定狀態下，在差分矩陣上做二維前綴和應該得到原矩陣，因為這是一對逆運算。

二維前綴和的公式是這樣的：

\(s(i, j) = s(i - 1, j) + s(i, j - 1) - s(i - 1, j - 1) + a(i, j)\)。

所以，設 \(a\) 是原數組，\(d\) 是差分數組，有：

\(a(i, j) = a(i - 1, j) + a(i, j - 1) - a(i - 1, j - 1) + d(i, j)\)

移項就得到二維差分的公式了。

\(d(i, j) = a(i, j) - a(i - 1, j) - a(i, j - 1) + a(i - 1, j - 1)\)。

這樣以來，對左上角 \((x_1, y_1)\)，右下角 \((x_2, y_2)\) 的子矩陣區間加 \(v\)，相當於在差分數組上，對 \(d(x_1, y_1)\) 和 \(d(x_2 + 1, y_2 + 1)\) 分別單點加 \(v\)，對 \(d(x_2 + 1, y_1)\) 和 \(d(x_1, y_2 + 1)\) 分別單點加 \(-v\)。

至於原因，把這四個 \(d\) 分別用定義式表示出來，分析一下每項的變化即可。

舉個例子吧，初始差分數組為 \(0\)，給 \(a(2, 2) \ldots a(3, 4)\) 子矩陣加 \(v\) 後差分數組會變為：

\[ \begin{pmatrix}0&0&0&0&0\\0&v&0&0&-v\\0&0&0&0&0\\0&-v&0&0&v\end{pmatrix} \]

（其中 \(a(2, 2) \ldots a(3, 4)\) 這個子矩陣恰好是上面位於中心的 \(2 \times 3\) 大小的矩陣。）

因此，子矩陣加的做法是：轉化為差分數組上的四個單點加操作。

現在考慮查詢子矩陣和：

對於點 \((x, y)\)，它的二維前綴和可以表示為：

\[ \sum_{i = 1}^x\sum_{j = 1}^y\sum_{h = 1}^i\sum_{k = 1}^j d(h, k) \]

原因就是差分的前綴和的前綴和就是原本的前綴和。

和一維樹狀數組的「區間加區間和」問題類似，統計 \(d(h, k)\) 的出現次數，為 \((x - h + 1) \times (y - k + 1)\)。

然後接着推導：

\[ \begin{aligned} &\sum_{i = 1}^x\sum_{j = 1}^y\sum_{h = 1}^i\sum_{k = 1}^j d(h, k) \\=&\sum_{i = 1}^x\sum_{j = 1}^y d(i, j) \times (x - i + 1) \times (y - j + 1) \\=&\sum_{i = 1}^x\sum_{j = 1}^y d(i, j) \times (xy + x + y + 1) - d(i, j) \times i \times (y + 1) - d(i, j) \times j \times (x + 1) + d(i, j) \times i \times j \end{aligned} \]

所以我們需維護四個樹狀數組，分別維護 \(d(i, j)\)，\(d(i, j) \times i\)，\(d(i, j) \times j\)，\(d(i, j) \times i \times j\) 的和信息。

當然了，和一維同理，如果只需要子矩陣加求單點值，維護一個差分數組然後詢問前綴和就足夠了。

下面給出代碼：

實現 
 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
typedef long long ll;
ll t1[N][N], t2[N][N], t3[N][N], t4[N][N];

void add(ll x, ll y, ll z) {
  for (int X = x; X <= n; X += lowbit(X))
    for (int Y = y; Y <= m; Y += lowbit(Y)) {
      t1[X][Y] += z;
      t2[X][Y] += z * x;  // 注意是 z * x 而不是 z * X，後面同理
      t3[X][Y] += z * y;
      t4[X][Y] += z * x * y;
    }
}

void range_add(ll xa, ll ya, ll xb, ll yb,
               ll z) {  //(xa, ya) 到 (xb, yb) 子矩陣
  add(xa, ya, z);
  add(xa, yb + 1, -z);
  add(xb + 1, ya, -z);
  add(xb + 1, yb + 1, z);
}

ll ask(ll x, ll y) {
  ll res = 0;
  for (int i = x; i; i -= lowbit(i))
    for (int j = y; j; j -= lowbit(j))
      res += (x + 1) * (y + 1) * t1[i][j] - (y + 1) * t2[i][j] -
             (x + 1) * t3[i][j] + t4[i][j];
  return res;
}

ll range_ask(ll xa, ll ya, ll xb, ll yb) {
  return ask(xb, yb) - ask(xb, ya - 1) - ask(xa - 1, yb) + ask(xa - 1, ya - 1);
}

權值樹狀數組及應用

我們知道，普通樹狀數組直接在原序列的基礎上構建，\(c_6\) 表示的就是 \(a[5 \ldots 6]\) 的區間信息。

然而事實上，我們還可以在原序列的權值數組上構建樹狀數組，這就是權值樹狀數組。

什麼是權值數組？

一個序列 \(a\) 的權值數組 \(b\)，滿足 \(b[x]\) 的值為 \(x\) 在 \(a\) 中的出現次數。

例如：\(a = (1, 3, 4, 3, 4)\) 的權值數組為 \(b = (1, 0, 2, 2)\)。

很明顯，\(b\) 的大小和 \(a\) 的值域有關。

若原數列值域過大，且重要的不是具體值而是值與值之間的相對大小關係，常 離散化 原數組後再建立權值數組。

另外，權值數組是原數組無序性的一種表示：它重點描述數組的元素內容，忽略了數組的順序，若兩數組只是順序不同，所含內容一致，則它們的權值數組相同。

因此，對於給定數組的順序不影響答案的問題，在權值數組的基礎上思考一般更直觀，比如 [NOIP2021] 數列。

運用權值樹狀數組，我們可以解決一些經典問題。

單點修改，查詢全局第 \(k\) 小

在此處只討論第 \(k\) 小，第 \(k\) 大問題可以通過簡單計算轉化為第 \(k\) 小問題。

該問題可離散化，如果原序列 \(a\) 值域過大，離散化後再建立權值數組 \(b\)。注意，還要把單點修改中的涉及到的值也一起離散化，不能只離散化原數組 \(a\) 中的元素。

對於單點修改，只需將對原數列的單點修改轉化為對權值數組的單點修改即可。具體來説，原數組 \(a[x]\) 從 \(y\) 修改為 \(z\)，轉化為對權值數組 \(b\) 的單點修改就是 \(b[y]\) 單點減 \(1\)，\(b[z]\) 單點加 \(1\)。

對於查詢第 \(k\) 小，考慮二分 \(x\)，查詢權值數組中 \([1, x]\) 的前綴和，找到 \(x_0\) 使得 \([1, x_0]\) 的前綴和 \(< k\) 而 \([1, x_0 + 1]\) 的前綴和 \(\ge k\)，則第 \(k\) 大的數是 \(x_0 + 1\)（注：這裏認為 \([1, 0]\) 的前綴和是 \(0\)）。

這樣做時間複雜度是 \(\Theta(\log^2n)\) 的。

考慮用倍增替代二分。

設 \(x = 0\)，\(\mathrm{sum} = 0\)，枚舉 \(i\) 從 \(\log_2n\) 降為 \(0\)：

  • 查詢權值數組中 \([x + 1 \ldots x + 2^i]\) 的區間和 \(t\)。
  • 如果 \(\mathrm{sum} + t < k\)，擴展成功，\(x \gets x + 2^i\)，\(\mathrm{sum} \gets \mathrm{sum} + t\)；否則擴展失敗，不操作。

這樣得到的 \(x\) 是滿足 \([1 \ldots x]\) 前綴和 \(< k\) 的最大值，所以最終 \(x + 1\) 就是答案。

看起來這種方法時間效率沒有任何改善，但事實上，查詢 \([x + 1 \ldots x + 2^i]\) 的區間和只需訪問 \(c[x + 2^i]\) 的值即可。

原因很簡單，考慮 \(\operatorname{lowbit}(x + 2^i)\)，它一定是 \(2^i\)，因為 \(x\) 之前只累加過 \(2^j\) 滿足 \(j > i\)。因此 \(c[x + 2^i]\) 表示的區間就是 \([x + 1 \ldots x + 2^i]\)。

如此以來，時間複雜度降低為 \(\Theta(\log n)\)。

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// 權值樹狀數組查詢第 k 小
int kth(int k) {
  int sum = 0, x = 0;
  for (int i = log2(n); ~i; --i) {
    x += 1 << i;                    // 嘗試擴展
    if (x >= n || sum + t[x] >= k)  // 如果擴展失敗
      x -= 1 << i;
    else
      sum += t[x];
  }
  return x + 1;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
# 權值樹狀數組查詢第 k 小
def kth(k):
    sum = 0; x = 0
    i = log2(n)
    while ~i:
        x = x + (1 << i) # 嘗試擴展
        if x >= n or sum + t[x] >= k: # 如果擴展失敗
            x = x - (1 << i)
        else:
            sum = sum + t[x]
    return x + 1

全局逆序對（全局二維偏序）

全局逆序對也可以用權值樹狀數組巧妙解決。問題是這樣的：給定長度為 \(n\) 的序列 \(a\)，求 \(a\) 中滿足 \(i < j\) 且 \(a[i] > a[j]\) 的數對 \((i, j)\) 的數量。

該問題可離散化，如果原序列 \(a\) 值域過大，離散化後再建立權值數組 \(b\)。

我們考慮從 \(n\) 到 \(1\) 倒序枚舉 \(i\)，作為逆序對中第一個元素的索引，然後計算有多少個 \(j > i\) 滿足 \(a[j] < a[i]\)，最後累計答案即可。

事實上，我們只需要這樣做（設當前 \(a[i] = x\)）：

  • 查詢 \(b[1 \ldots x - 1]\) 的前綴和，即為左端點為 \(a[i]\) 的逆序對數量。
  • \(b[x]\) 自增 \(1\)；

原因十分自然：出現在 \(b[1 \ldots x-1]\) 中的元素一定比當前的 \(x = a[i]\) 小，而 \(i\) 的倒序枚舉，自然使得這些已在權值數組中的元素，在原數組上的索引 \(j\) 大於當前遍歷到的索引 \(i\)。

用例子説明，\(a = (4, 3, 1, 2, 1)\)。

\(i\) 按照 \(5 \to 1\) 掃：

  • \(a[5] = 1\)，查詢 \(b[1 \ldots 0]\) 前綴和，為 \(0\)，\(b[1]\) 自增 \(1\)，\(b = (1, 0, 0, 0)\)。
  • \(a[4] = 2\)，查詢 \(b[1 \ldots 1]\) 前綴和，為 \(1\)，\(b[2]\) 自增 \(1\)，\(b = (1, 1, 0, 0)\)。
  • \(a[3] = 1\)，查詢 \(b[1 \ldots 0]\) 前綴和，為 \(0\)，\(b[1]\) 自增 \(1\)，\(b = (2, 1, 0, 0)\)。
  • \(a[2] = 3\)，查詢 \(b[1 \ldots 2]\) 前綴和，為 \(3\)，\(b[3]\) 自增 \(1\)，\(b = (2, 1, 1, 0)\)。
  • \(a[1] = 4\)，查詢 \(b[1 \ldots 3]\) 前綴和，為 \(4\)，\(b[4]\) 自增 \(1\)，\(b = (2, 1, 1, 1)\)。

所以最終答案為 \(0 + 1 + 0 + 3 + 4 = 8\)。

注意到，遍歷 \(i\) 後的查詢 \(b[1 \ldots x - 1]\) 和自增 \(b[x]\) 的兩個步驟可以顛倒，變成先自增 \(b[x]\) 再查詢 \(b[1 \ldots x - 1]\)，不影響答案。兩個角度來解釋：

  • 對 \(b[x]\) 的修改不影響對 \(b[1 \ldots x - 1]\) 的查詢。
  • 顛倒後，實質是在查詢 \(i \le j\) 且 \(a[i] > a[j]\) 的數對數量，而 \(i = j\) 時不存在 \(a[i] > a[j]\)，所以 \(i \le j\) 相當於 \(i < j\)，所以這與原來的逆序對問題是等價的。

如果查詢非嚴格逆序對（\(i < j\) 且 \(a[i] \ge a[j]\)）的數量，那就要改為查詢 \(b[1 \ldots x]\) 的和，這時就不能顛倒兩步了，還是兩個角度來解釋：

  • 對 \(b[x]\) 的修改 影響 對 \(b[1 \ldots x]\) 的查詢。
  • 顛倒後，實質是在查詢 \(i \le j\) 且 \(a[i] \ge a[j]\) 的數對數量，而 \(i = j\) 時恆有 \(a[i] \ge a[j]\)，所以 \(i \le j\) 不相當於 \(i < j\)，與原問題 不等價。

如果查詢 \(i \le j\) 且 \(a[i] \ge a[j]\) 的數對數量，那這兩步就需要顛倒了。

另外，對於原逆序對問題，還有一種做法是正着枚舉 \(j\)，查詢有多少 \(i < j\) 滿足 \(a[i] > a[j]\)。做法如下（設 \(x = a[j]\)）：

  • 查詢 \(b[x + 1 \ldots V]\)（\(V\) 是 \(b\) 的大小，即 \(a\) 的值域（或離散化後的值域））的區間和。
  • 將 \(b[x]\) 自增 \(1\)。

原因：出現在 \(b[x + 1 \ldots V]\) 中的元素一定比當前的 \(x = a[j]\) 大，而 \(j\) 的正序枚舉，自然使得這些已在權值數組中的元素，在原數組上的索引 \(i\) 小於當前遍歷到的索引 \(j\)。

樹狀數組維護不可差分信息

比如維護區間最值等。

注意，這種方法雖然碼量小，但單點修改和區間查詢的時間複雜度均為 \(\Theta(\log^2n)\)，比使用線段樹的時間複雜度 \(\Theta(\log n)\) 劣。

區間查詢

我們還是基於之前的思路，從 \(r\) 沿着 \(\operatorname{lowbit}\) 一直向前跳，但是我們不能跳到 \(l\) 的左邊。

因此，如果我們跳到了 \(c[x]\)，先判斷下一次要跳到的 \(x - \operatorname{lowbit}(x)\) 是否小於 \(l\)：

  • 如果小於 \(l\)，我們直接把 \(\boldsymbol{a[x]}\) 單點 合併到總信息裏，然後跳到 \(c[x - 1]\)。
  • 如果大於等於 \(l\)，説明沒越界，正常合併 \(c[x]\)，然後跳到 \(c[x - \operatorname{lowbit}(x)]\) 即可。

下面以查詢區間最大值為例，給出代碼：

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
int getmax(int l, int r) {
  int ans = 0;
  while (r >= l) {
    ans = max(ans, a[r]);
    --r;
    for (; r - lowbit(r) >= l; r -= lowbit(r)) {
      // 注意，循環條件不要寫成 r - lowbit(r) + 1 >= l
      // 否則 l = 1 時，r 跳到 0 會死循環
      ans = max(ans, C[r]);
    }
  }
  return ans;
}

可以證明，上述算法的時間複雜度是 \(\Theta(\log^2n)\)。

時間複雜度證明

考慮 \(r\) 和 \(l\) 不同的最高位，一定有 \(r\) 在這一位上為 \(1\)，\(l\) 在這一位上為 \(0\)（因為 \(r \ge l\)）。

如果 \(r\) 在這一位的後面仍然有 \(1\)，一定有 \(r - \operatorname{lowbit}(r) \ge l\)，所以下一步一定是把 \(r\) 的最低位 \(1\) 填為 \(0\)；

如果 \(r\) 的這一位 \(1\) 就是 \(r\) 的最低位 \(1\)，無論是 \(r \gets r - \operatorname{lowbit}(r)\) 還是 \(r \gets r - 1\)，\(r\) 的這一位 \(1\) 一定會變為 \(0\)。

因此，\(r\) 經過至多 \(\log n\) 次變換後，\(r\) 和 \(l\) 不同的最高位一定可以下降一位。所以，總時間複雜度是 \(\Theta(\log^2n)\)。

單點更新

注

請先理解樹狀數組樹形態的以下兩條性質，再學習本節。

  • 設 \(u = s \times 2^{k + 1} + 2^k\)，則其兒子數量為 \(k = \log_2\operatorname{lowbit}(u)\)，編號分別為 \(u - 2^t(0 \le t < k)\)。
  • \(u\) 的所有兒子對應 \(c\) 的管轄區間恰好拼接成 \([l(u), u - 1]\)。

關於這兩條性質的含義及證明，都可以在本頁面的 樹狀數組與其樹形態的性質 一節找到。

更新 \(a[x]\) 後，我們只需要更新滿足在樹狀數組樹形態上，滿足 \(y\) 是 \(x\) 的祖先的 \(c[y]\)。

對於最值（以最大值為例），一種常見的錯誤想法是，如果 \(a[x]\) 修改成 \(p\)，則將所有 \(c[y]\) 更新為 \(\max(c[y], p)\)。下面是一個反例：\((1, 2, 3, 4, 5)\) 中將 \(5\) 修改成 \(4\)，最大值是 \(4\)，但按照上面的修改這樣會得到 \(5\)。將 \(c[y]\) 直接修改為 \(p\) 也是錯誤的，一個反例是，將上面例子中的 \(3\) 修改為 \(4\)。

事實上，對於不可差分信息，不存在通過 \(p\) 直接修改 \(c[y]\) 的方式。這是因為修改本身就相當於是把舊數從原區間「移除」，然後加入一個新數。「移除」時對區間信息的影響，相當於做「逆運算」，而不可差分信息不存在「逆運算」，所以無法直接修改 \(c[y]\)。

換句話説，對每個受影響的 \(c[y]\)，這個區間的信息我們必定要重構了。

考慮 \(c[y]\) 的兒子們，它們的信息一定是正確的（因為我們先更新兒子再更新父親），而這些兒子又恰好組成了 \([l(y), y - 1]\) 這一段管轄區間，那再合併一個單點 \(a[y]\) 就可以合併出 \([l(y), y]\)，也就是 \(c[y]\) 了。這樣，我們能用至多 \(\log n\) 個區間重構合併出每個需要修改的 \(c\)。

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
void update(int x, int v) {
  a[x] = v;
  for (int i = x; i <= n; i += lowbit(i)) {
    // 枚舉受影響的區間
    C[i] = a[i];
    for (int j = 1; j < lowbit(i); j *= 2) {
      C[i] = max(C[i], C[i - j]);
    }
  }
}

容易看出上述算法時間複雜度為 \(\Theta(\log^2n)\)。

建樹

可以考慮拆成 \(n\) 個單點修改，\(\Theta(n\log^2n)\) 建樹。

也有 \(\Theta(n)\) 的建樹方法，見本頁面 \(\Theta(n)\) 建樹 一節的方法一。

Tricks

\(\Theta(n)\) 建樹

以維護區間和為例。

方法一：

每一個節點的值是由所有與自己直接相連的兒子的值求和得到的。因此可以倒着考慮貢獻，即每次確定完兒子的值後，用自己的值更新自己的直接父親。

實現 
1
2
3
4
5
6
7
8
// Θ(n) 建樹
void init() {
  for (int i = 1; i <= n; ++i) {
    t[i] += a[i];
    int j = i + lowbit(i);
    if (j <= n) t[j] += t[i];
  }
}

1
2
3
4
5
6
7
# Θ(n) 建樹
def init():
    for i in range(1, n + 1):
        t[i] = t[i] + a[i]
        j = i + lowbit(i)
        if j <= n:
            t[j] = t[j] + t[i]

方法二：

前面講到 \(c[i]\) 表示的區間是 \([i-\operatorname{lowbit}(i)+1, i]\)，那麼我們可以先預處理一個 \(\mathrm{sum}\) 前綴和數組，再計算 \(c\) 數組。

實現 
1
2
3
4
5
6
// Θ(n) 建樹
void init() {
  for (int i = 1; i <= n; ++i) {
    t[i] = sum[i] - sum[i - lowbit(i)];
  }
}

1
2
3
4
# Θ(n) 建樹
def init():
    for i in range(1, n + 1):
        t[i] = sum[i] - sum[i-lowbit(i)]

時間戳優化

對付多組數據很常見的技巧。若每次輸入新數據都暴力清空樹狀數組，就可能會造成超時。因此使用 \(\mathrm{tag}\) 標記，存儲當前節點上次使用時間（即最近一次是被第幾組數據使用）。每次操作時判斷這個位置 \(\mathrm{tag}\) 中的時間和當前時間是否相同，就可以判斷這個位置應該是 \(0\) 還是數組內的值。

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
// 時間戳優化
int tag[MAXN], t[MAXN], Tag;

void reset() { ++Tag; }

void add(int k, int v) {
  while (k <= n) {
    if (tag[k] != Tag) t[k] = 0;
    t[k] += v, tag[k] = Tag;
    k += lowbit(k);
  }
}

int getsum(int k) {
  int ret = 0;
  while (k) {
    if (tag[k] == Tag) ret += t[k];
    k -= lowbit(k);
  }
  return ret;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
# 時間戳優化
tag = [0] * MAXN; t = [0] * MAXN; Tag = 0
def reset():
    Tag = Tag + 1
def add(k, v):
    while k <= n:
        if tag[k] != Tag:
            t[k] = 0
        t[k] = t[k] + v
        tag[k] = Tag
        k = k + lowbit(k)
def getsum(k):
    ret = 0
    while k:
        if tag[k] == Tag:
            ret = ret + t[k]
        k = k - lowbit(k)
    return ret

例題

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：HeRaNO, Zhoier, Ir1d, Xeonacid, wangdehu, ouuan, ranwen, ananbaobeichicun, Ycrpro, dbxxx-oi
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用