{%hackmd @YuRen-tw/article-theme %}

# 結合律演算法

這裡記錄一些有關結合律的演算法。

> :::spoiler 目錄
> [TOC]
> :::

## 前言
### 基本代數定義
這裡用比較偏集合論的語言來描述。

<div class="definition" data-info="二元運算">

對於集合 $S$，稱 $\otimes$ 是 $S$ 上的二元運算，代表它是二元函數 $\otimes\colon S \times S \to S$。
這時就說 $S$ 配備上 $\otimes$ 組成了代數結構 $\langle S, \otimes\rangle$。
</div>

我們常會要求二元運算 $\otimes$ 滿足封閉性：對任意 $a, b\in S$ 都有 $a \otimes b \in S$，這時我們也會說 $S$ 對二元運算 $\otimes$ 封閉。
而這裡把 $\otimes$ 定為 $S$ 上的二元運算直接蘊含了封閉性，所以我們不必再額外設定這個條件。

> 我們可以用 $S^{S\times S}$ 代表搜集 $S$ 上二元運算的集合，其中 $B^A$ 代表搜集所有函數 $A \to B$ 的集合。
> 在 Haskell 中習慣表示為 `S → S → S`，這是因為 $S^{S\times S}$ 與 $(S^S)^S$ 同構，而後者更方便於 Haskell 中使用。

<div class="definition" data-info="結合律與半群">

對於代數結構 $\langle S, \otimes\rangle$，如果任意 $x, y, z\in S$ 都滿足 \\[(x \otimes y) \otimes z = x \otimes (y \otimes z),\\]我們就說 $\otimes$ 滿足結合律，同時也稱 $\langle S, \otimes\rangle$ 為半群（semigroup）。
</div>

結合律是常見於各種代數結構中的性質，這代表這篇筆記提到的演算法也可以適用於很多情境。
有了結合律，我們也不必使用括號表明運算順序了。

還有一個常見的性質稱為交換律，也就是對任意 $x, y \in S$ 都有 $x \otimes y = y \otimes x$。
並不是所有代數結構都滿足交換律，但如果滿足就會稱是可交換的（commutative）。

<div class="definition" data-info="單位元素、反元素、群">

對於代數結構 $\langle S, \otimes\rangle$，如果 $e\in S$ 對任意 $x\in S$ 都滿足 \\[x \otimes e = x = e \otimes x,\\] 我們就稱 $e$ 為 $\langle S, \otimes\rangle$ 的單位元素。
對於 $x\in S$，如果 $y\in S$ 滿足 \\[x \otimes y = e = y \otimes x,\\] 我們就說 $x$ 可逆，同時也稱 $y$ 為 $x$ 的反元素。

當半群 $\langle S, \otimes\rangle$ 有單位元素 $e$，我們就稱代數結構 $\langle S, \otimes, e\rangle$ 為么半群（monoid）。
若每個元素都可逆，我們就稱 $\langle S, \otimes, e\rangle$ 為群（group）。
</div>

> Monoid 在國教院網站被翻譯成相當白話的「具單位元素半群」。
> 在這邊我們選用另一個常見翻譯「么半群」，其中「么」對應「mono-」，大概是單位元素的意思。

### 例子
我們可以從既有的半群得到其他半群：
- 對於半群 $\langle S, \otimes \rangle$ 與代數結構 $\langle A, \star \rangle$，若有同態 $\varphi\colon S \to A$，也就是對任意 $a, b\in S$ 都滿足 $\varphi(a \otimes b) = \varphi(a) \star \varphi(b)$，則 $\langle \operatorname{img}(\varphi), \star \rangle$ 也是半群。
- 若 $S$ 有單位元素 $e$，則 $\langle \operatorname{img}(\varphi), \star, \varphi(e) \rangle$ 是么半群。
- 對於么半群 $\langle M_1, \otimes_1, e_1 \rangle$ 與 $\langle M_2, \otimes_2, e_2 \rangle$，若有同態 $\varphi\colon M_1 \to M_2$，則 $\langle \operatorname{ker}(\varphi), \otimes_1, e_1 \rangle$ 也是么半群。
- 其中 $\operatorname{ker}(\varphi) := \{ a\in M_1 \mid \varphi(a) = e_2 \}$。
- 對於半群 $\langle S, \otimes \rangle$，若子集 $X \subseteq S$ 對 $\otimes$ 封閉，則 $\langle X, \otimes \rangle$ 也是半群。
- 若有單位元素 $e$ 並且也屬於 $X$，則 $\langle X, \otimes, e \rangle$ 是么半群。
- 對於半群 $\langle S_1, \otimes_1 \rangle$ 與 $\langle S_2, \otimes_2 \rangle$，它們的積 $\langle S_1 \times S_2, \otimes \rangle$ 也是半群，其中 \\[ (a_1, a_2) \otimes (b_1, b_2) := (a_1 \otimes_1 b_1, a_2 \otimes_2 b_2). \\]
- 若各有單位元素 $e_1$ 與 $e_2$，則 $\langle S_1 \times S_2, \otimes, (e_1, e_2) \rangle$ 是么半群。
- 對於集合 $X$ 與半群 $\langle S, \otimes \rangle$，代數結構 $\langle S^X, \otimes \rangle$ 是半群，其中 \\[ (f \otimes g)(x) := f(x) \otimes g(x). \\]
- 若有單位元素 $e$，則 $\langle S^X, \otimes, c_e \rangle$ 是么半群，其中令 $c_e\colon x \mapsto e$。

下面列舉的大多數例子其實是更複雜的代數結構，在這裡不把詳細定義寫出。

#### 合成
<div class="invisible-box">

$\DeclareMathOperator{\id}{id}$
</div>

合成其實就是串接。
為了描述抽象又通用的概念，這裡講的合成（composition）使用了範疇論的語言。
範疇（category）包含了兩類事物：物件（object）與態射（morphism）。
任意的態射 $f\colon X \to Y$ 與 $g\colon Y \to Z$ 都存在它們的合成 $g \circ f\colon X \to Z$，其中代表合成的二元運算 $\circ$ 被要求滿足結合律。
而每個物件 $X$ 也都有單位態射 $\id_X$，使得對任意態射 $f\colon X \to Y$ 都有 \\[ \id_Y \circ f = f = f \circ \id_X. \\]
於是我們有以下的例子：
- 對於範疇 $\mathcal{C}$ 與物件 $X$，代數結構 $\langle \operatorname{Hom}_\mathcal{C}(X, X), \circ, \id_X\rangle$ 是么半群。
- 事實上任何的么半群都可以轉化成單物件範疇。
- 對於集合 $S$，代數結構 $\langle S^S, \circ, \id_S\rangle$ 是么半群。
- 令 $S$ 搜集所有字串，則代數結構 $\langle S, ⧺, \varepsilon\rangle$ 是么半群。
- 二元運算 $⧺$ 代表字串串接、$\varepsilon$ 代表空字串。

#### 環
環（ring）是配備了加法（$+$）與乘法（$\cdot$）的代數結構。
環 $\langle R, +, {}\cdot{}, 0, 1\rangle$ 包含了可交換的加法群 $\langle R, +, 0\rangle$ 與乘法么半群 $\langle R, {}\cdot{}, 1\rangle$。

下面列舉的各個例子都是環，也就是說都包含有加法群與乘法半群：
- 整數 $\mathbb{Z}$、模 $n$ 整數 $\mathbb{Z}/n\mathbb{Z}$、有理數 $\mathbb{Q}$、實數 $\mathbb{\mathbb R}$、複數 $\mathbb{\mathbb C}$ 都是環。
- 任意環 $R$ 都有多項式環 $\langle R[x], +, {}\cdot{}, 0, 1\rangle$。
- 其中 $R[x]$ 搜集係數屬於環 $R$ 的一元多項式。
- 任意環 $R$ 都有矩陣環 $\langle M_n(R), +, {}\cdot{}, O_n, I_n\rangle$。
- 其中 $M_n(R)$ 搜集元素屬於環 $R$ 的 $n$ 階方陣。
- 布林環 $\langle \mathbb{B}, \oplus, \land, \mathbf{0}, \mathbf{1}\rangle$。
- 其中 $\oplus$ 代表 XOR。
- 要注意與下面的布林代數不同。

#### 格
格（lattice）是配備了交（$\wedge$，meet）與接（$\vee$，join）的代數結構。
格 $\langle L, \wedge, \vee \rangle$ 包含了兩個可交換的半群 $\langle L, \wedge\rangle$ 與 $\langle L, \vee\rangle$。
若只包含其中一個二元運算，那麼就稱為半格（semilattice）。

對於偏序 $\langle P, \le\rangle$，如果任兩個元素都有最大下界或最小上界，那麼 $\langle P, \inf\rangle$ 或 $\langle P, \sup\rangle$ 也會形成半格。
另一方面，半格都能定義出對應的偏序結構：\\[a \le b \iff a \wedge b = a.\\]
如果對應的偏序結構有最大元素 $\top$ 或最小元素 $\bot$，那麼 $\langle L, \wedge, \top\rangle$ 或 $\langle L, \vee, \bot\rangle$ 就是么半群，而 $\langle L, \wedge, \vee, \bot, \top\rangle$ 也稱為有界格。

下面列舉的各個例子都是格，也就是說都包含有兩種半群：
- 布林代數 $\langle \mathbb{B}, \land, \lor, \mathbf{0}, \mathbf{1}\rangle$ 是有界格。
- 要注意與上面的布林環不同。
- 整除關係 $\langle \mathbb{Z}, \gcd, \operatorname{lcm}, 1, 0\rangle$ 是有界格。
- 任意集合 $S$ 都有有界格 $\langle 2^S, \cap, \cup, \varnothing, S\rangle$。
- 其中 $2^S$ 搜集所有 $S$ 的子集。
- 任意全序 $\langle T, \le\rangle$ 都有格 $\langle T, \min, \max\rangle$。

## 冪
<div class="definition" data-info="冪">

對於半群 $\langle S, \otimes\rangle$ 以及任意 $x \in S$，我們令「次方」為 \\[ x^n := \bigotimes_{i=1}^n x = \overbrace{x \otimes x \otimes \dotsb \otimes x}^n. \\] 如果是在么半群 $\langle S, \otimes, e\rangle$ 內，我們定義 $x^0 := e$。
</div>

我們會發現因為 $\otimes$ 滿足結合律，所以「次方」也會滿足指數律：\\[
x^{m+n} = x^m \otimes x^n,\quad
x^{mn} = (x^m)^n.
\\]

### 快速冪
> 這個演算法也被稱為平方求冪法（exponentiating by squaring）。
> 而對於把 $\otimes$ 運算稱為「加法」的代數結構，這類算法也稱為 double-and-add。

快速冪是一個快速算「次方」的演算法，核心概念就是利用指數律來降低 $\otimes$ 的運算次數。
比如說把 $x^{14}$ 變成 $(x^7)^2$ 或 $(x^2)^7$，像這樣一直遞迴拆解下去，我們就能用 $O(\log n)$ 次的 $\otimes$ 運算計算出 $x^n$。
我們通常會選用 $2$ 來除，這多半是因為對現實中機器而言，除以 $2$ 與判斷奇偶數是非常容易的操作。
而依照拆解的方式又可分為以下兩類。

#### 第一類算法：$x^{2k} = (x^k)^2$
例如 $x^{14} = ((x^2 \otimes x)^2 \otimes x)^2$。
這裡使用以下的規則：\\[
x^n = \begin{cases}
x, & n = 1;\\
x^k \otimes x^k, & n = 2k;\\
x^k \otimes x^k \otimes x, & n = 2k+1.
\end{cases}
\\]
當我們是在么半群 $\langle S, \otimes, e\rangle$ 中計算時，將第一條式子改為 $x^0 = e$。

#### 第二類算法：$x^{2k} = (x^2)^k$
例如 $x^{14} = x^8 \otimes x^4 \otimes x^2$，其中 $x^{2n}$ 都是從已經算過的 $x^n$「平方」之後算出來的。
這裡使用以下的規則：\\[
x^n = \begin{cases}
x, & n = 1;\\
(x \otimes x)^k, & n = 2k;\\
(x \otimes x)^k \otimes x, & n = 2k+1.
\end{cases}
\\]
當我們是在么半群 $\langle S, \otimes, e\rangle$ 中計算時，將第一條式子改為 $x^0 = e$。

## 區間查詢
對於半群 $\langle S, \otimes\rangle$ 以及 $S$ 中的序列 $(x_i)_{i=1}^n$，我們令 \\[ x(a, b) := \bigotimes_{i=a}^b x_i = x_a \otimes x_{a+1} \otimes \dotsb \otimes x_b. \\] 下面的各個小節主要關注在查詢多個 $x(a, b)$ 時，如何有效率地求出各個結果而不總是從頭計算。
更進一步地，我們也關注在查詢之間更改 $x_i$ 的情形，這被稱為「動態區間查詢」問題。

<div class="invisible-box">

$\DeclareMathOperator{\root}{root}$
$\DeclareMathOperator{\parent}{parent}$
$\DeclareMathOperator{\child}{child}$
$\DeclareMathOperator{\left}{left}$
$\DeclareMathOperator{\right}{right}$
$\DeclareMathOperator{\query}{\mathtt{query}}$
$\DeclareMathOperator{\update}{\mathtt{update}}$
</div>

下面的小節會用到一種結構稱為樹。我們會將樹 $T$ 上的資料結構考慮為節點到值的函數 $\tau\colon T \to S$。
需要注意的是，這裡所說的樹是無窮大的樹，而資料結構 $\tau$ 的定義域則往往是有限的。
如果這個樹是二元樹，我們會特別記為 $T_2$。
其他符號定義如下：
<div class="definition" data-info="樹">

對於樹 $T$ 與其上的節點 $v \in T$，我們定義
- $\root(T)$ 為 $T$ 的根結點。
- $\parent(v)$ 為 $v$ 的父結點。
- $\child_i(v)$ 為 $v$ 的第 $i$ 個子結點。
- 特別地當在 $v \in T_2$ 時，
- $\left(v) := \child_1(v)$ 為 $v$ 的左子結點。
- $\right(v) := \child_2(v)$ 為 $v$ 的右子結點。
</div>

### 部分和
> 在某些地方也被稱為前綴和（prefix sum）。

> *Work In Progress*...

#### 與 scan 的關聯
函數型程式語言裡可能設計有高階函式 $\operatorname{\mathtt{scan}}\colon A^{A\times B}\times A\times B^n\to A^{n+1}$ 使得 \\[ \operatorname{\mathtt{scan}}(\star, a, (b_i)) = (a, a\star b_1, (a \star b_1) \star b_2, \dots, ((a \star b_1) \star \dotsb) \star b_n). \\]

> 在 Haskell 裡面寫作 `scanl`，後面的 `l` 是左結合的意思，另外還有 `scanl1: (a → a → a) → [a] → [a]` 更符合我們說的部分和。

其中作為參數之一的二元運算 $\star\colon A \times B \to A$ 並不必是半群運算，所以 $\mathtt{scan}$ 看似與半群上的部分和不太一樣。
然而這只是程式語言的設計選擇而已，我們可以考慮以下的定義：
- 令 $\sigma_b\colon a \mapsto a \star b$，也就是說 $\sigma_b$ 代表在右邊乘上 $b$ 的運算。
- $S := \{ \sigma_b \mid b \in B\} \cup \{ \id_A \}$。

能驗證 $\langle S, \circ, \operatorname{id}_A\rangle$ 是么半群，於是 $\mathtt{scan}$ 可以視為 $\langle S, \circ, \id_A\rangle$ 上的部分和： \\[ \operatorname{\mathtt{scan}}(\star, a, (b_i)) = \sigma_b(0,i)(a). \\]

### 二分區間樹
> 據說是演算法競賽選手發明的資料結構，競賽圈通常稱其為線段樹（segment tree）。
> 然而這個名稱似乎有歧義，在這裡我們姑且叫它二分區間樹。

<div class="definition" data-info="二分區間樹">

二分區間樹 $\tau_x\colon T_2 \to S$ 是由以下兩個規則定義的二元樹資料結構：
1. $\tau_x(\root(T_2)) = x(1, n)$；
2. 如果 $\tau_x(v) = x(a, b)$ 且 $a \lt b$，令 $c = \lfloor(a+b)/2\rfloor$，那麼 \\[ \tau_x(\left(v)) = x(a, c),\quad \tau_x(\right(v)) = x(c+1, b).\\]
</div>

我們會發現 $\tau_x(v) = \tau_x(\left(v)) \otimes \tau_x(\right(v))$，讓我們能自下而上建構 $\tau_x$。
每一個節點都代表對應一個區間值，我們就寫作 $\tau_x(v) = x(\ell_v, r_v)$。

因為每個子節點都是二分區間之後的結果，這個樹狀資料結構會是非常平衡的。
當序列長度是 $n$ 時，定義域的節點數會是 $2n-1$ 個，最大深度則是 $\lceil \log_2 n\rceil$。
例如當 $n = 7$ 時，我們可以用以下的圖示表示二分區間樹 $\tau_x$：

graph {
  ranksep=.3
  nodesep=.14
  node [fontname="sans" fontsize="12pt"
        shape=rectangle height=0 margin="0,0.1"]
  { rank=same
    node [width=6.26]
    "x(1,7)"
  }
  { rank=same
    node [width=3.06]
    edge [style=invis]
    "x(1,4)" -- "x(5,7)"
  }
  { rank=same
    node [width=1.46]
    edge [style=invis]
    "x(1,2)" -- "x(3,4)" --
    "x(5,6)" -- "x(7,7)"
  }
  { rank=same
    node [width=.66]
    edge [style=invis]
    "x(1,1)" -- "x(2,2)" --
    "x(3,3)" -- "x(4,4)" --
    "x(5,5)" -- "x(6,6)"
  }

  "x(1,7)" -- { "x(1,4)" "x(5,7)" }
  "x(1,4)" -- { "x(1,2)" "x(3,4)" }
  "x(1,2)" -- { "x(1,1)" "x(2,2)" }
  "x(3,4)" -- { "x(3,3)" "x(4,4)" }
  "x(5,7)" -- { "x(5,6)" "x(7,7)" }
  "x(5,6)" -- { "x(5,5)" "x(6,6)" }
}

> 演算法競賽圈常有人用序列模擬二元樹，也就是令 $\root(T_2) = 1$、$\left(i) = 2i$、$\right(i) = 2i+1$。
> 然而二分區間樹的定義會使最深的一層在序列上變得分散，例如當 $n = 2^m+2$ 時，序列最後一項有定義的是 $\tau_x(2^m\cdot 3+1) = x_{2^{m-1}+3}$。
> 這就是競賽圈實作時序列長度常會開到 $4n$ 的原因……

不過這並不代表建構 $\tau_x$ 都必須自下而上把 $2n-1$ 個節點通通跑過。
如果序列 $(x_i)$ 在么半群 $\langle S, \otimes, e\rangle$ 中，我們可以先令二分區間樹為常數函數 $\tau_e\colon v \mapsto e$。
如果序列中只有 $k$ 項不是 $e$，那麼對 $\tau_e$ 施以下一小節的單項更改來一步步建構出我們需要的 $\tau_x$ 只需要更改不超過 $k(\lceil \log_2 n\rceil+1)$ 個節點。
也就是說如果非 $e$ 項占約全部的 $2/(\lceil \log_2 n\rceil+1)$ 以下，這樣做都會比較省步驟。

> 在演算法競賽圈，這種建立方式稱為「動態開點」。

#### 單項更改
我們可以透過以下算法做單項更改：\begin{align*}
\tau_y &= \update(i, y_i, \tau_x)\\[5pt]
\update(i, y_i, \tau_x)(v) &= \begin{cases}
y_i, &\ell_v = i = r_v;\\
\tau_y(\left(v)) \otimes \tau_x(\right(v)), &i \le r_{\left(v)};\\
\tau_x(\left(v)) \otimes \tau_y(\right(v)), &\ell_{\right(v)} \le i;\\
\tau_x(v), &\text{otherwise}.
\end{cases}
\end{align*}

<div class="example">

當 $n = 7$ 時，若要更改 $x_3$，那麼 $x(3, 3)$、$x(3, 4)$、$x(1, 4)$、$x(1, 7)$ 對應的值都需要重新計算。

  graph {
    ranksep=.3
    nodesep=.14
    node [fontname="sans" fontsize="12pt"
          shape=rectangle height=0 margin="0,0.1"]
    { rank=same
      node [width=6.26]
      "x(1,7)"
    }
    { rank=same
      node [width=3.06]
      edge [style=invis]
      "x(1,4)" -- "x(5,7)"
    }
    { rank=same
      node [width=1.46]
      edge [style=invis]
      "x(1,2)" -- "x(3,4)" --
      "x(5,6)" -- "x(7,7)"
    }
    { rank=same
      node [width=.66]
      edge [style=invis]
      "x(1,1)" -- "x(2,2)" --
      "x(3,3)" -- "x(4,4)" --
      "x(5,5)" -- "x(6,6)"
    }

    "x(1,7)" -- { "x(1,4)" "x(5,7)" }
    "x(1,4)" -- { "x(1,2)" "x(3,4)" }
    "x(1,2)" -- { "x(1,1)" "x(2,2)" }
    "x(3,4)" -- { "x(3,3)" "x(4,4)" }
    "x(5,7)" -- { "x(5,6)" "x(7,7)" }
    "x(5,6)" -- { "x(5,5)" "x(6,6)" }

    "x(1,7)" [style=filled color="#f6b763" penwidth=2.5 fillcolor="#fdc56566"]
    "x(1,4)" [style=filled color="#f6b763" penwidth=2.5 fillcolor="#fdc56566"]
    "x(3,4)" [style=filled color="#f6b763" penwidth=2.5 fillcolor="#fdc56566"]
    "x(3,3)" [style=filled color="#f6b763" penwidth=2.5 fillcolor="#fdc56566"]
  }

</div>

#### 區間查詢
我們可以透過以下算法得出特定的區間值 $x(a, b)$：\begin{align*}
x(a, b) &= \query(a, b, \tau_x, \root(T_2))\\[5pt]
\query(a, b, \tau_x, v) &= \begin{cases}
\tau_x(v), &a \le \ell_v \le r_v \le b;\\
L, &b \le r_{\left(v)};\\
R, &\ell_{\right(v)} \le a;\\
L \otimes R, &\text{otherwise}.
\end{cases}\\
L &= \query(a, b, \tau_x, \left(v))\\
R &= \query(a, b, \tau_x, \right(v))
\end{align*}

<div class="example">

當 $n = 7$ 時，若要求 $x(2, 6)$，就要計算 $x(2, 2) \otimes x(3, 4) \otimes x(5, 6)$。

  graph {
    ranksep=.3
    nodesep=.14
    node [fontname="sans" fontsize="12pt"
          shape=rectangle height=0 margin="0,0.1"]
    { rank=same
      node [width=6.26]
      "x(1,7)"
    }
    { rank=same
      node [width=3.06]
      edge [style=invis]
      "x(1,4)" -- "x(5,7)"
    }
    { rank=same
      node [width=1.46]
      edge [style=invis]
      "x(1,2)" -- "x(3,4)" --
      "x(5,6)" -- "x(7,7)"
    }
    { rank=same
      node [width=.66]
      edge [style=invis]
      "x(1,1)" -- "x(2,2)" --
      "x(3,3)" -- "x(4,4)" --
      "x(5,5)" -- "x(6,6)"
    }

    "x(1,7)" -- { "x(1,4)" "x(5,7)" }
    "x(1,4)" -- { "x(1,2)" "x(3,4)" }
    "x(1,2)" -- { "x(1,1)" "x(2,2)" }
    "x(3,4)" -- { "x(3,3)" "x(4,4)" }
    "x(5,7)" -- { "x(5,6)" "x(7,7)" }
    "x(5,6)" -- { "x(5,5)" "x(6,6)" }

    "x(2,2)" [style=filled color="#f6b763" penwidth=2.5 fillcolor="#fdc56566"]
    "x(3,4)" [style=filled color="#f6b763" penwidth=2.5 fillcolor="#fdc56566"]
    "x(5,6)" [style=filled color="#f6b763" penwidth=2.5 fillcolor="#fdc56566"]
  }

</div>

#### 惰性區間更改
顯而易見，如果我們要同時更改一個區間的值，不斷使用單點更改的方法將會耗費大量的步驟重新建構 $\tau_x$。
不過如果我們所要處理的更改操作有足夠好的性質，那我們可以就利用惰性運算解決這個問題。

對於更改序列的操作 $f\colon (x_i) \mapsto (y_i)$，我們希望能直接算出區間值 $y(a, b)$，不必自下而上完全重建新的 $\tau_y$，並且只有在有需要求子區間值的時候才往下更改。
也就是說，假設 $\mathcal{F}$ 是我們要處理的一類更改操作，我們就要找出 $\Phi\colon S \times\Lambda \to S$、$\phi_0\colon \mathcal{F}\to\Lambda$、$\phi_L, \phi_R\colon \Lambda\to\Lambda$，滿足以下兩個性質：
1. $\tau_y(\root(T_2)) = \Phi(\tau_x(\root(T_2)), \phi_0(f))$；
2. 如果 $\tau_y(v) = \Phi(\tau_x(v), t)$，就有 \begin{align*}
\tau_y(\left(v))
&= \Phi(\tau_x(\left(v)), \phi_L(t)),\\
\tau_y(\right(v))
&= \Phi(\tau_x(\right(v)), \phi_R(t)).
\end{align*}
> 在演算法競賽圈中稱 $t\in\Lambda$ 為懶惰標記，而 $\phi_L$ 與 $\phi_R$ 可能被稱為 `push`，表示把標記往下一層推進。

### 二元索引樹
> 由計算機科學家 P. M. Fenwick 提出，也被稱為 Fenwick 樹。
> 演算法競賽圈通常稱它為二元索引樹（binary indexed tree，縮寫為 BIT）。

<div class="definition" data-info="二元索引樹">

二元索引樹 $\tau_x\colon T \to S$ 是啥？
</div>

<div class="example">

當 $n = 13$ 時，我們可以用以下的圖示表示二元索引樹 $\tau_x$：

  graph {
    node [fontname="sans" shape=square]
    {
      node [color="#00000055" shape=circle]
      0
    }
    0 -- { 1 2 4 8 }
    2 -- 3
    4 -- { 5 6 }
    6 -- 7
    8 -- { 9 10 12 }
    10 -- 11
    12 -- 13
  }

  graph {
    node [fontname="sans" shape=square]
    8 12
    {
      node [color="#00000055" shape=circle]
      16 14
    }
    16 -- { 8 12 14 }
    8 -- { 4 6 7 }
    4 -- { 2 3 }
    2 -- 1
    6 -- 5
    12 -- { 10 11 }
    10 -- 9
    14 -- 13
  }

  graph {
    node [fontname="sans" shape=square]
    10 13
    {
      node [color="#00000055" shape=circle]
      14
    }
    8 -- { 4 12 }
    4 -- { 2 6 }
    2 -- { 1 3 }
    6 -- { 5 7 }
    12 -- { 10 14 }
    10 -- { 9 11 }
    14 -- { 13 }
  }

</div>

> *Work In Progress*...