5 木構造配列

コース内容#

接頭辞和配列と差分配列#

【仮定】元の配列 $a$：$a_i,\ i\in [0,\ n]$、注意 $a_0=0$[さもなければ差分配列の接頭辞和は元の配列と等しくない]

【得られる】

接頭辞和配列 $S$：$S_i = \sum_{k=0}^{i}{a_i}$、容易に得られる $a_i = S_i - S_{i-1}$[差分]
差分配列 $X$：$X_i=a_i-a_{i-1}$、容易に得られる $a_i=\sum_{k=0}^{i} X_i$[接頭辞和]

【観察】

接頭辞和配列、差分配列は情報を増やすことはなく、情報の別の表現形式に過ぎない
ある配列が分かれば、他の配列を導出できる
- 配列 $a$ が分かれば：—— 接頭辞和 ——>$S$ 配列、—— 差分 ——>$X$ 配列
- $S$ 配列が分かれば：—— 差分 ——>$a$ 配列
- $X$ 配列が分かれば：—— 接頭辞和 ——>$a$ 配列
[PS] 接頭辞和操作と差分操作は、実際には二つの逆操作である
❗ しかし、異なる表現形式は異なる操作に対して異なる時間計算量に対応し、以下を参照

【問題導入】

① 元の配列区間和操作

$a$ 配列上の操作：$O (n)$
$S$ 配列上の操作：$O (1)$、$S_i-S_{j-1}$ から $a$ 配列の区間和 $[j,\ i]$ が得られる

② 元の配列区間修正操作

修正前：
- $a$ 配列上：$a_0,a_1,a_2,a_3,a_4,a_5,a_6$
- $X$ 配列上：$X_1=a_1-a_0,X_2=a_2-a_1,X_3=a_3-a_2,X_4=a_4-a_3,X_5=a_5-a_4,X_6=a_6-a_5$
修正後：[区間加算]
- $a$ 配列上：$a_0,a_1,a_2 [+d],a_3 [+d],a_4 [+d],a_5 [+d],a_6$
- $X$ 配列上：$X_1=a_1-a_0,X_2=a_2-a_1 [+d],X_3=a_3-a_2,X_4=a_4-a_3,X_5=a_5-a_4,X_6=a_6-a_5 [-d]$
見ての通り
- $a$ 配列上の操作：$O (n)$
- $X$ 配列上の操作：$O (1)$

【結論】

接頭辞和配列：区間和操作の最適化
差分配列：区間要素修正操作の最適化

【考察】❗

接頭辞和配列の単点修正効率は $O (n)$ である。なぜなら、変化点とその後のすべての接頭辞和要素の値を修正する必要があるからである
接頭辞和配列の要素値は、以前の元の配列のすべての項と関係がある！では、この関係をどのように弱めることができるのか？

👉樹状配列：上記の関係を弱め、クエリ効率を少し失う [トレードオフ]

lowbit 関数#

【樹状配列の鍵】

$lowbit (i)$：$i$ という数字の二進数表現の最後の 1 の位の重みを表す
計算式：$lowbit (i) = i\ &\ (-i) = i\ &\ (\sim i + 1)$
例：$lowbit (10010000)$
- 最も右の 1 の位置を得る、非常に巧妙である
負数は補数表現法を使用する：[負数の] 補数 = [正数の] 反数 + 1
- 例えば：$-3 = ~3 + 1 = ~0011 + 1 = 1101$
- ❗ 補数表現法は減算を加算に変える [コンピュータには減算がない]

樹状配列#

⭐樹状配列は本質的に接頭辞和配列の最適化であり、主に単点修正操作に現れる

直感的比較：接頭辞和配列#

樹状配列中の $C [i]$ は $a [i]$ から始まる前 $lowbit (i)$ 項の和を表す
樹状配列はよりフラットである
両者の空間消費は同じである

接頭辞和クエリ#

接頭辞和：$S [i]=S [i-lowbit (i)]+C [i]$
例えば
- $S[7]=S[7-1]+C[7]=S[6-2]+C[6]+C[7]=C[4]+C[6]+C[7]$
- $S[12]=S[12-4]+C[12]=C[8]+C[12]$
時間計算量：$O (log\ n)$
[PS]$(i)_2$ 中の 1 の個数、すなわち接頭辞和の構成要素の数

単点修正#

修正位置 $i$ の値を修正するには、$f (i)=i + lowbit (i)$ の位置を繰り返し修正する必要がある：$C [i],\ C [f (i)],\ C [f (f (i))],\ ...,\ until\ index\gt n$
例えば
- $a [1]$ を修正する：$C [1],C [2],C [4],C [8]$ < 普通の接頭辞和配列では、前 8 項を修正する必要がある >
時間計算量：$O (log\ n)$

小結#

$lowbit ()$ 関数：非常に重要
二つの操作
- 接頭辞和クエリ：前方に統計を取り、毎回 $i$ の前の位を調べる ——> $i - lowbit (i)$、$i=0$ になるまで
- 単点の修正：後方に修正し、毎回 $i$ の後の位を調べる ——> $i + lowbit (i)$、$i>n$ になるまで
時間効率
- 接頭辞和クエリ：$O (log\ n)$、単点修正：$O (log\ n)$
- 最も普通の接頭辞和配列と比較して、クエリは悪化し、単点修正は改善され、総合的な時間計算量は改善される
使用前提：必ず接頭辞和問題に変換可能であること

授業中の練習#

HZOJ-329：弱化された整数問題#

サンプル入力

サンプル出力

思考
- 区間修正、単点クエリ操作を含む
  - 区間修正👉差分配列の単点操作 ① [最適、上記を参照]
  - 単点クエリ👉差分配列の接頭辞和 ②
- 接頭辞和 ②を維持しつつ、単点修正 ①を行うために
  - ⭐樹状配列を使用して、元の配列の差分配列を維持することができる
  - もちろんセグメントツリーを使用することもできる
コード
- ❗区間修正操作を差分配列に置き換え、【単点修正】に変換する；単点クエリ操作を差分配列の求める【接頭辞和】に変換する
- 樹状配列のコードを学ぶこと、その実装は一般的に変わらない [汎用性が非常に高い]
  - ⭐単点修正、接頭辞和を求める
- 差分配列を保存し、前の要素を記録するために pre 変数を使用する
- [PS] 差分配列と接頭辞和配列のインデックスは一般的に 1 から始まる。なぜなら、両者の第 0 位は 0 であるからである

HZOJ-330：強化された整数問題#

サンプル入力

サンプル出力

思考
- 区間修正、区間クエリ操作を含む
  - 区間修正👉差分配列の単点修正 ① [前の問題と同様：OJ-329]
  - しかし、区間クエリはどうするのか？👉二つの接頭辞和 ②、以下を参照
- 区間クエリ問題の変換
  - ① 差分配列を導入したため、区間和問題を差分配列に基づいて変換する必要がある
  - ② 区間和 $Query (l,r)=S (r)-S (l-1)$、したがって $S$ から $X$[差分配列] への変換を重点的に分析する
  - ③ 以下の等式を導出する
    - $\begin{aligned}&S_i=\sum_{k=1}^ia_k=\sum_{k=1}^{i}\sum_{y=1}^{k}{X_y}\&=\sum_{k=1}^i[(i+1)X_k-k\times X_k]=(i+1)\sum_{k=1}^iX_k-\sum_{k=1}^i(k\times X_k)\end{aligned}$
    - 第一行の等式は明らかである
    - 第二行の等式の導出は以下を参照
      - $\sum_{k=1}^{i}\sum_{y=1}^{k}{X_y}\ (Ⅰ)$ に対して、$i=4$ と仮定し、$k$ の値を列挙する
      - 観察から、$(Ⅰ)=\sum_{k=1}^{i}[(i-k+1)\times X_k]$ が得られる
      - 変数をグループ化して配置することで、得られる
  - ④ $Y_k=k\times X_k$ とすると、$S_i=(i+1)\sum_{k=1}^iX_k-\sum_{k=1}^iY_k$
  - 【結論】$S_i$ は2 つの差分配列に関連する接頭辞和配列から得られるため、$Query (l,r)$ 問題を解決することができる
    - 二つの樹状配列を維持する必要がある
- [PS] 維持する二つの樹状配列は、すべて差分配列に関連しているため、区間修正時の時間効率を保証する
コード
- 全体の考え方に注目し、番号 $0\to 2$ を整理する
- 主な方法
  - add、query メソッド：樹状配列の基本操作、単点修正 && 接頭辞和を求める
  - modify メソッド：二つの樹状配列を同時に維持する
  - S メソッド：二つの差分配列の接頭辞和を通じて、元の列の接頭辞和を求める [導出した公式に注目]
- [考察] 維持する二つの樹状配列はすべて差分配列に関連しているため、区間修正時の樹状配列の時間計算量は $O (log\ n)$ レベルである [2 × 2 回の単点修正]
  - ❗ 区間クエリを考えると、元の配列を使用する方が便利であり、元の配列と差分配列の樹状配列を維持することができる。しかし、区間修正時に元の配列の樹状配列を維持する場合、時間計算量は $O (n \times log\ n)$ レベルであり、元の配列を使用する方が良い。これは $O (n)$ レベルに対応する
- [PS] 操作情報を char で受け取る場合、scanf の際に以前の改行文字の存在を考慮する必要がある
  - しかし、cin にはこの問題はない；文字配列を使用してもこの問題はない

追加知識点#

樹状配列 VS.セグメントツリー
- 樹状配列のコードは少ない
- 空間的には ——$n：4n$[元の配列のサイズは $n$]

ヒント#

接頭辞積版樹状配列を連想することができる
- 加算と乗算には本質的な違いはなく、どちらも積性関数である
- [PS] 初期の 0 を 1 に変え、すべての += 操作を *= 操作に変える
樹状配列の原理は何か？—— 知乎
- $lowbit (i)$ との関係を理解する