樹狀數組及其各種擴展

什么是樹狀數組

一種簡單的區間數據結構, 可以維護簡單修改的數組.

樹狀數組長什么樣

\(\displaystyle val_{x} = \sum a_{i}, i \in (x - \operatorname{lowbit}(x), x]\)

注意是左開右閉區間, \(\displaystyle \LARGE i \in (x - \operatorname{lowbit}(x), x]\)

單點修

現在要給 \(a_{3} := a_{3} + 1\).

首先, 觀察關于 \(a_{3}\) 的結點有哪些.

可以看出, \(val_{3}, val_{4}, val_{8}\) 和 \(a_{3}\) 有關.

那么有什么東西可以從 \(3\) 到 \(4\) 再到 \(8\) 呢?

觀察二進制.

\(0011 = 3 \newline 0100 = 4 \newline 1000 = 8\)

可以看到, 上面的數加上最右邊的\(1\)就是下面的數.

那怎么獲取到最右邊的\(1\)呢?

\(\operatorname{lowbit}(x) = x \& -x\).

為什么這樣就能獲得最右邊的\(1\)呢?

首先, 負數在C語言里用補碼存儲, 可以自己嘗試, \(\forall x \in \Z\) 有 \(-x = \sim x + 1\).

那么, 看 \(3\) 和 \(-3\) 按位與.

\(0011 \newline 1101\)

可以發現, 這時候就是取到了 \(3\) 最右邊的 \(1\).

證明.

\(x\) 取反后所有的 \(1\) 變成 \(0\), \(0\) 變成 \(1\).

\(0011 \newline 1100\)

加一后最后面的 \(1\) 全部進位, 一直到第一個原來的 \(1\).

\(1100 \newline 1101\)

然后按位與 \(x\).

\(0011 \newline 1101\)

就是 \(\operatorname{lowbit}(x)\).

\(3 + \operatorname{lowbit}(3) = 4\)

\(4 + \operatorname{lowbit}(4) = 8\)

所以最后的單點修代碼就寫完了.

void chg(int x, ll k) {
  f1 (i, x, N, i & -i) // for (int i(x); i <= N; i += i & -i)
    val[i] += k;
}

區間查

查詢 \(a\) 的 \(1\) 到 \(7\) 的和.

再次觀察樹狀數組, 哪些結點加起來正好是 \(1\) 到 \(7\).

很顯然 \(val_{4}\), \(val_{6}\), \(val_{7}\) 加起來是 \(a\) 的 \(1\) 到 \(7\).

可以想到, \(7 - \operatorname{lowbit}(7) = 6\), \(6 - \operatorname{lowbit}(6) = 4\), \(4 - \operatorname{lowbit}(4) = 0\).

那么區間查的代碼就寫出來了.

ll qry(int x) { ll s(0LL);
  f2 (i, x, 1, i & -i) // for (int i(x); i >= 1; i -= i & -i)
    s += val[i];
  return s;
}

什么? 查 \(x\) 到\(y\), 不一定是 \(1\) 到 \(x\)?

查了 \(1\) 到 \(y\) 再扣掉 \(1\) 到 \(x - 1\) 不就好了? 前綴和不是基本功嗎?

方法1, 查 \(1\) 到 \(y\) 在扣掉 \(1\) 到 \(x - 1\).

ll qry(int x, int y) {
  return qry(y) - qry(x - 1);
}

方法2, 直接在查詢時扣掉.

ll qry(int x, int y) { ll s(0LL);
  f2 (i, y, 1, i & -i)
    s += val[i];
  f2 (i, x - 1, 1, i & -i)
    s -= val[i];
  return s;
}

二維樹狀數組

單點修改, 矩陣求和, Defad覺得只需要說一下二維前綴和.

\(val_{i, j}\) 為 \(a_{1, 1}\) 到 \(a_{i, j}\) 的和.

觀察二維前綴和, 如何求第二行第二個矩陣的和.

扣掉上面和左邊, 加上左上即可.

void chg(int x, int y, ll k) {
  f1 (i, x, N, i & -i)
    f2 (j, y, M, j & -j)
      val[i][j] += k;
}

ll qry(int x, int y) { ll s(0LL);
  f2 (i, x, 1, i & -i)
    f2 (j, y, 1, j & -j)
      s += val[i][j];
  return s;
}

ll qry(int x_1, int y_1, int x_2, int y_2) {
  return qry(x_2, y_2)
        - qry(x_2, y_1 - 1)
        - qry(x_1 - 1, y_2)
        + qry(x_1 - 1, y_1 - 1);
}

擴展樹狀數組, 區間修區間查

推式子網上有很多, Defad不太喜歡在板子題上推式子, 所以這里直接用了.

\(\displaystyle val0_{x} = \sum_{i = 1}^{x} a_{i}\)

\(\displaystyle val1_{x} = \sum_{i = 1}^{x} a_{i} * i\)

修改滿足差分性質, 在 \(x\) 和 \(y + 1\) 處修改即可.

這里有一個可以偷懶的地方, 差分修改如果 \(y = N\) 是不能在 \(y + 1\) 修改的 (容易RE), 但是for (int i(y + 1); i <= N; i += i & -i)在 \(y = N\) 時甚至進不了for循環, 也就不會有任何問題.

void chg(int x, ll k) {
  f1 (i, x, N, i & -i) {
    val[0][i] += k;
    val[1][i] += k * x;
  }
}

void chg(int x, int y, ll k) {
  chg(x, k); chg(y + 1, -k);
}

查詢就是 \(val0_{i} * (x + 1) - val1_{i}\) 即可.

\(x\)到\(y\)還是查\(1\)到\(y\)在扣掉\(1\)到\(x - 1\).

ll qry(int x) { ll s(0LL);
  f2 (i, x, 1, i & -i) {
    s += val[0][i] * (x + 1) - val[1][i];
  }
  return s;
}

ll qry(int x, int y) { ll s(0LL);
  f2 (i, y, 1, i & -i) {
    s += val[0][i] * (y + 1) - val[1][i];
  }
  f2 (i, x - 1, 1, i & -i) {
    s -= val[0][i] * x - val[1][i];
  }
  return s;
}

擴展樹狀數組的二維版本, 矩陣修矩陣查

那么我們看一下二維差分的矩陣修改.

可以嘗試出左上角 \(+ k\), 右上角的右邊 \(- k\), 左下角的下面 \(- k\), 右下角的右下 \(+ k\)就可以實現矩陣加.

void chg(int x, int y, ll k) {
  f1 (i, x, N, i & -i) {
    f1 (j, y, M, j & -j) {
      val[0][i][j] += k;
      val[1][i][j] += k * x;
      val[2][i][j] += k * y;
      val[3][i][j] += k * x * y;
    }
  }
}

void chg(int x1, int y1, int x2, int y2, ll k) {
  chg(x1, y1, k); chg(x2 + 1, y1, -k);
  chg(x1, y2 + 1, -k); chg(x2 + 1, y2 + 1, k);
}

矩陣和還是一樣的二維前綴和, 就是給一下這里怎么求二維前綴和.

ll qry(int x, int y) { ll s(0LL);
  f2 (i, x, 1, i & -i) {
    f2 (j, y, 1, j & -j) {
      s += val[0][i][j] * (x + 1) * (y + 1);
      s -= val[1][i][j] * (y + 1);
      s -= val[2][i][j] * (x + 1);
      s += val[3][i][j];
    }
  }
  return s;
}

ll qry(int x1, int y1, int x2, int y2) {
  return qry(x2, y2) - qry(x2, y1 - 1) - qry(x1 - 1, y2) + qry(x1 - 1, y1 - 1);
}

樹狀數組和線段樹

Defad個人認為樹狀數組和線段樹關系不大.

對比樹狀數組和線段樹.

雖然樹狀數組是長得像刪掉所有右兒子的線段樹, 但樹狀數組和線段樹的思想是完全不同的.

樹狀數組每個結點管長度為 \(\operatorname{lowbit}(x)\) 的區間, 顯然是倍增.

線段樹是每個結點分給左兒子一半, 分給右兒子一半, 很明顯是分治.

所以Defad認為樹狀數組和線段樹是關系不大的并且本質不同, 可能發明樹狀數組受了線段樹的啟發但是思想是不同的.

然后看復雜度.

樹狀數組的時間復雜度 (本節討論區間操作) 就是常數極小的 \(2\) 倍 \(\log N\).

線段樹的時間復雜度是常數極大 (Defad還沒學會ZKW線段樹, 不過非遞歸線段樹常數也挺大) 的 \(\log N\).

樹狀數組的空間復雜度是 \(2\) 倍 \(N\) .

線段樹的空間復雜度是 \(4\) 倍 \(N\), 還有懶標記就是 \(8\) 倍 \(N\).

所以說樹狀數組是卡時空利器.

習題

樹狀數組2

VJudge LuoGu

差分之后單點加區間查.

或者直接區間修單點查.

上帝造題的七分鐘

VJudge LuoGu

經典矩陣加求矩陣和.