結合律演算法

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

目錄

• 結合律演算法
  • 前言
    • 基本代數定義
    • 例子
  • 冪
    • 快速冪
  • 區間查詢
    • 部分和
    • 二分區間樹
    • 二元索引樹

前言

基本代數定義

這裡用比較偏集合論的語言來描述。

對於集合

$S$，稱

$\otimes$ 是

$S$ 上的二元運算，代表它是二元函數

$\otimes :S\times S\to S$。
這時就說

$S$ 配備上

$\otimes$ 組成了代數結構

$⟨S,\otimes ⟩$。

我們常會要求二元運算

$\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 中使用。

對於代數結構

$⟨S,\otimes ⟩$，如果任意

$x,y,z\in S$ 都滿足

$$(x\otimes y)\otimes z=x\otimes (y\otimes z),$$我們就說

$\otimes$ 滿足結合律，同時也稱

$⟨S,\otimes ⟩$ 為半群（semigroup）。

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

還有一個常見的性質稱為交換律，也就是對任意

$x,y\in S$ 都有

$x\otimes y=y\otimes x$。
並不是所有代數結構都滿足交換律，但如果滿足就會稱是可交換的（commutative）。

對於代數結構

$⟨S,\otimes ⟩$，如果

$e\in S$ 對任意

$x\in S$ 都滿足

$$x\otimes e=x=e\otimes x,$$ 我們就稱

$e$ 為

$⟨S,\otimes ⟩$ 的單位元素。
對於

$x\in S$，如果

$y\in S$ 滿足

$$x\otimes y=e=y\otimes x,$$ 我們就說

$x$ 可逆，同時也稱

$y$ 為

$x$ 的反元素。

當半群

$⟨S,\otimes ⟩$ 有單位元素

$e$，我們就稱代數結構

$⟨S,\otimes ,e⟩$ 為么半群（monoid）。
若每個元素都可逆，我們就稱

$⟨S,\otimes ,e⟩$ 為群（group）。

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

例子

我們可以從既有的半群得到其他半群：

• 對於半群
  $⟨S,\otimes ⟩$ 與代數結構
  $⟨A,\star ⟩$，若有同態
  $\phi :S\to A$，也就是對任意
  $a,b\in S$ 都滿足
  $\phi (a\otimes b)=\phi (a)\star \phi (b)$，則
  $⟨\mathrm{img}(\phi ),\star ⟩$ 也是半群。
  • 若
    $S$ 有單位元素
    $e$，則
    $⟨\mathrm{img}(\phi ),\star ,\phi (e)⟩$ 是么半群。
• 對於么半群
  $⟨M_1,{\otimes }_1,e_1⟩$ 與
  $⟨M_2,{\otimes }_2,e_2⟩$，若有同態
  $\phi :M_1\to M_2$，則
  $⟨\ker (\phi ),{\otimes }_1,e_1⟩$ 也是么半群。
  • 其中
    $\ker (\phi ):=\{a\in M_1\mid \phi (a)=e_2\}$。
• 對於半群
  $⟨S,\otimes ⟩$，若子集
  $X\subseteq S$ 對
  $\otimes$ 封閉，則
  $⟨X,\otimes ⟩$ 也是半群。
  • 若有單位元素
    $e$ 並且也屬於
    $X$，則
    $⟨X,\otimes ,e⟩$ 是么半群。
• 對於半群
  $⟨S_1,{\otimes }_1⟩$ 與
  $⟨S_2,{\otimes }_2⟩$，它們的積
  $⟨S_1\times S_2,\otimes ⟩$ 也是半群，其中
  $$(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$，則
    $⟨S_1\times S_2,\otimes ,(e_1,e_2)⟩$ 是么半群。
• 對於集合
  $X$ 與半群
  $⟨S,\otimes ⟩$，代數結構
  $⟨S^X,\otimes ⟩$ 是半群，其中
  $$(f\otimes g)(x):=f(x)\otimes g(x).$$
  • 若有單位元素
    $e$，則
    $⟨S^X,\otimes ,c_e⟩$ 是么半群，其中令
    $c_e:x\mapsto e$。

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

合成

$$

合成其實就是串接。
為了描述抽象又通用的概念，這裡講的合成（composition）使用了範疇論的語言。
範疇（category）包含了兩類事物：物件（object）與態射（morphism）。
任意的態射

$f:X\to Y$ 與

$g:Y\to Z$ 都存在它們的合成

$g\circ f:X\to Z$，其中代表合成的二元運算

$\circ$ 被要求滿足結合律。
而每個物件

$X$ 也都有單位態射

${\mathrm{id}}_X$，使得對任意態射

$f:X\to Y$ 都有

$${\mathrm{id}}_Y\circ f=f=f\circ {\mathrm{id}}_X.$$
於是我們有以下的例子：

• 對於範疇
  $\mathcal{C}$ 與物件
  $X$，代數結構
  $⟨{\mathrm{Hom}}_{\mathcal{C}}(X,X),\circ ,{\mathrm{id}}_X⟩$ 是么半群。
  • 事實上任何的么半群都可以轉化成單物件範疇。
• 對於集合
  $S$，代數結構
  $⟨S^S,\circ ,{\mathrm{id}}_S⟩$ 是么半群。
• 令
  $S$ 搜集所有字串，則代數結構
  $⟨S,⧺,\epsilon ⟩$ 是么半群。
  • 二元運算
    $⧺$ 代表字串串接、
    $\epsilon$ 代表空字串。

環

環（ring）是配備了加法（

$+$）與乘法（

$\cdot$）的代數結構。
環

$⟨R,+,\cdot ,0,1⟩$ 包含了可交換的加法群

$⟨R,+,0⟩$ 與乘法么半群

$⟨R,\cdot ,1⟩$。

下面列舉的各個例子都是環，也就是說都包含有加法群與乘法半群：

• 整數
  $\mathbb{Z}$、模
  $n$ 整數
  $\mathbb{Z}/n\mathbb{Z}$、有理數
  $\mathbb{Q}$、實數
  $\mathbb{R}$、複數
  $\mathbb{C}$ 都是環。
• 任意環
  $R$ 都有多項式環
  $⟨R[x],+,\cdot ,0,1⟩$。
  • 其中
    $R[x]$ 搜集係數屬於環
    $R$ 的一元多項式。
• 任意環
  $R$ 都有矩陣環
  $⟨M_n(R),+,\cdot ,O_n,I_n⟩$。
  • 其中
    $M_n(R)$ 搜集元素屬於環
    $R$ 的
    $n$ 階方陣。
• 布林環
  $⟨\mathbb{B},\oplus ,\wedge ,\mathbf{0},\mathbf{1}⟩$。
  • 其中
    $\oplus$ 代表 XOR。
  • 要注意與下面的布林代數不同。

格

格（lattice）是配備了交（

$\wedge$，meet）與接（

$\vee$，join）的代數結構。
格

$⟨L,\wedge ,\vee ⟩$ 包含了兩個可交換的半群

$⟨L,\wedge ⟩$ 與

$⟨L,\vee ⟩$。
若只包含其中一個二元運算，那麼就稱為半格（semilattice）。

對於偏序

$⟨P,\le ⟩$，如果任兩個元素都有最大下界或最小上界，那麼

$⟨P,inf⟩$ 或

$⟨P,sup⟩$ 也會形成半格。
另一方面，半格都能定義出對應的偏序結構：

$$a\le b⟺a\wedge b=a.$$
如果對應的偏序結構有最大元素

$\mathrm{\top }$ 或最小元素

$\mathrm{\perp }$，那麼

$⟨L,\wedge ,\mathrm{\top }⟩$ 或

$⟨L,\vee ,\mathrm{\perp }⟩$ 就是么半群，而

$⟨L,\wedge ,\vee ,\mathrm{\perp },\mathrm{\top }⟩$ 也稱為有界格。

下面列舉的各個例子都是格，也就是說都包含有兩種半群：

• 布林代數
  $⟨\mathbb{B},\wedge ,\vee ,\mathbf{0},\mathbf{1}⟩$ 是有界格。
  • 要注意與上面的布林環不同。
• 整除關係
  $⟨\mathbb{Z},gcd,\mathrm{lcm},1,0⟩$ 是有界格。
• 任意集合
  $S$ 都有有界格
  $⟨2^S,\cap ,\cup ,\varnothing ,S⟩$。
  • 其中
    $2^S$ 搜集所有
    $S$ 的子集。
• 任意全序
  $⟨T,\le ⟩$ 都有格
  $⟨T,min,max⟩$。

冪

對於半群

$⟨S,\otimes ⟩$ 以及任意

$x\in S$，我們令「次方」為

$$x^n:=\underset{i=1}{\overset{n}{⨂}}x=\stackrel{n}{\overbrace{x\otimes x\otimes \cdots \otimes x}}.$$ 如果是在么半群

$⟨S,\otimes ,e⟩$ 內，我們定義

$x^0:=e$。

我們會發現因為

$\otimes$ 滿足結合律，所以「次方」也會滿足指數律：

$$x^{m+n}=x^m\otimes x^n,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{array}{ll}x,& n=1;\\ x^k\otimes x^k,& n=2k;\\ x^k\otimes x^k\otimes x,& n=2k+1.\end{array}$$
當我們是在么半群

$⟨S,\otimes ,e⟩$ 中計算時，將第一條式子改為

$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{array}{ll}x,& n=1;\\ (x\otimes x{)}^k,& n=2k;\\ (x\otimes x{)}^k\otimes x,& n=2k+1.\end{array}$$
當我們是在么半群

$⟨S,\otimes ,e⟩$ 中計算時，將第一條式子改為

$x^0=e$。

區間查詢

對於半群

$⟨S,\otimes ⟩$ 以及

$S$ 中的序列

$(x_i{)}_{i=1}^n$，我們令

$$x(a,b):=\underset{i=a}{\overset{b}{⨂}}{x}_i=x_a\otimes x_{a+1}\otimes \cdots \otimes x_b.$$ 下面的各個小節主要關注在查詢多個

$x(a,b)$ 時，如何有效率地求出各個結果而不總是從頭計算。
更進一步地，我們也關注在查詢之間更改

$x_i$ 的情形，這被稱為「動態區間查詢」問題。

$$

$$

$$

$$

$$

$$

$$

下面的小節會用到一種結構稱為樹。我們會將樹

$T$ 上的資料結構考慮為節點到值的函數

$\tau :T\to S$。
需要注意的是，這裡所說的樹是無窮大的樹，而資料結構

$\tau$ 的定義域則往往是有限的。
如果這個樹是二元樹，我們會特別記為

$T_2$。
其他符號定義如下：

對於樹

$T$ 與其上的節點

$v\in T$，我們定義

• $\mathrm{root}(T)$ 為
  $T$ 的根結點。
• $\mathrm{parent}(v)$ 為
  $v$ 的父結點。
• ${\mathrm{child}}_i(v)$ 為
  $v$ 的第
  $i$ 個子結點。
• 特別地當在
  $v\in T_2$ 時，
  • $\mathrm{left}(v):={\mathrm{child}}_1(v)$ 為
    $v$ 的左子結點。
  • $\mathrm{right}(v):={\mathrm{child}}_2(v)$ 為
    $v$ 的右子結點。

部分和

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

Work In Progress…

與 scan 的關聯

函數型程式語言裡可能設計有高階函式

$\mathtt{scan}:A^{A\times B}\times A\times B^n\to A^{n+1}$ 使得

$$\mathtt{scan}(\star ,a,(b_i))=(a,a\star b_1,(a\star b_1)\star b_2,\dots ,((a\star b_1)\star \cdots )\star b_n).$$

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

其中作為參數之一的二元運算

$\star :A\times B\to A$ 並不必是半群運算，所以

$\mathtt{scan}$ 看似與半群上的部分和不太一樣。
然而這只是程式語言的設計選擇而已，我們可以考慮以下的定義：

• 令
  ${\sigma }_b:a\mapsto a\star b$，也就是說
  ${\sigma }_b$ 代表在右邊乘上
  $b$ 的運算。
• $S:=\{{\sigma }_b\mid b\in B\}\cup \{{\mathrm{id}}_A\}$。

能驗證

$⟨S,\circ ,{\mathrm{id}}_A⟩$ 是么半群，於是

$\mathtt{scan}$ 可以視為

$⟨S,\circ ,{\mathrm{id}}_A⟩$ 上的部分和：

$$\mathtt{scan}(\star ,a,(b_i))={\sigma }_b(0,i)(a).$$

二分區間樹

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

二分區間樹

${\tau }_x:T_2\to S$ 是由以下兩個規則定義的二元樹資料結構：

1. ${\tau }_x(\mathrm{root}(T_2))=x(1,n)$；
2. 如果
   ${\tau }_x(v)=x(a,b)$ 且
   $a<b$，令
   $c=\lfloor (a+b)/2\rfloor$，那麼
   $${\tau }_x(\mathrm{left}(v))=x(a,c),{\tau }_x(\mathrm{right}(v))=x(c+1,b).$$

我們會發現

${\tau }_x(v)={\tau }_x(\mathrm{left}(v))\otimes {\tau }_x(\mathrm{right}(v))$，讓我們能自下而上建構

${\tau }_x$。
每一個節點都代表對應一個區間值，我們就寫作

${\tau }_x(v)=x({\ell }_v,r_v)$。

因為每個子節點都是二分區間之後的結果，這個樹狀資料結構會是非常平衡的。
當序列長度是

$n$ 時，定義域的節點數會是

$2n-1$ 個，最大深度則是

$\lceil {\log }_{2}n\rceil$。
例如當

$n=7$ 時，我們可以用以下的圖示表示二分區間樹

${\tau }_x$：

演算法競賽圈常有人用序列模擬二元樹，也就是令

$\mathrm{root}(T_2)=1$、

$\mathrm{left}(i)=2i$、

$\mathrm{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)$ 在么半群

$⟨S,\otimes ,e⟩$ 中，我們可以先令二分區間樹為常數函數

${\tau }_e: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{array}{rl}{\tau }_y& =\mathtt{update}(i,y_i,{\tau }_x)\\ \mathtt{update}(i,y_i,{\tau }_x)(v)& =\{\begin{array}{ll}{y}_i,& {\ell }_v=i=r_v;\\ {\tau }_y(\mathrm{left}(v))\otimes {\tau }_x(\mathrm{right}(v)),& i\le r_{\mathrm{left}(v)};\\ {\tau }_x(\mathrm{left}(v))\otimes {\tau }_y(\mathrm{right}(v)),& {\ell }_{\mathrm{right}(v)}\le i;\\ {\tau }_x(v),& \text{otherwise}.\end{array}\end{array}$$

當

$n=7$ 時，若要更改

$x_3$，那麼

$x(3,3)$、

$x(3,4)$、

$x(1,4)$、

$x(1,7)$ 對應的值都需要重新計算。

區間查詢

我們可以透過以下算法得出特定的區間值

$x(a,b)$：

$$\begin{array}{rl}x(a,b)& =\mathtt{query}(a,b,{\tau }_x,\mathrm{root}(T_2))\\ \mathtt{query}(a,b,{\tau }_x,v)& =\{\begin{array}{ll}{\tau }_x(v),& a\le {\ell }_v\le r_v\le b;\\ L,& b\le r_{\mathrm{left}(v)};\\ R,& {\ell }_{\mathrm{right}(v)}\le a;\\ L\otimes R,& \text{otherwise}.\end{array}\\ L& =\mathtt{query}(a,b,{\tau }_x,\mathrm{left}(v))\\ R& =\mathtt{query}(a,b,{\tau }_x,\mathrm{right}(v))\end{array}$$

當

$n=7$ 時，若要求

$x(2,6)$，就要計算

$x(2,2)\otimes x(3,4)\otimes x(5,6)$。

惰性區間更改

顯而易見，如果我們要同時更改一個區間的值，不斷使用單點更改的方法將會耗費大量的步驟重新建構

${\tau }_x$。
不過如果我們所要處理的更改操作有足夠好的性質，那我們可以就利用惰性運算解決這個問題。

對於更改序列的操作

$f:(x_i)\mapsto (y_i)$，我們希望能直接算出區間值

$y(a,b)$，不必自下而上完全重建新的

${\tau }_y$，並且只有在有需要求子區間值的時候才往下更改。
也就是說，假設

$\mathcal{F}$ 是我們要處理的一類更改操作，我們就要找出

$\mathrm{\Phi }:S\times \mathrm{\Lambda }\to S$、

${\varphi }_0:\mathcal{F}\to \mathrm{\Lambda }$、

${\varphi }_L,{\varphi }_R:\mathrm{\Lambda }\to \mathrm{\Lambda }$，滿足以下兩個性質：

1. ${\tau }_y(\mathrm{root}(T_2))=\mathrm{\Phi }({\tau }_x(\mathrm{root}(T_2)),{\varphi }_0(f))$；
2. 如果
   ${\tau }_y(v)=\mathrm{\Phi }({\tau }_x(v),t)$，就有
   $$\begin{array}{rl}{\tau }_y(\mathrm{left}(v))& =\mathrm{\Phi }({\tau }_x(\mathrm{left}(v)),{\varphi }_L(t)),\\ {\tau }_y(\mathrm{right}(v))& =\mathrm{\Phi }({\tau }_x(\mathrm{right}(v)),{\varphi }_R(t)).\end{array}$$

在演算法競賽圈中稱

$t\in \mathrm{\Lambda }$ 為懶惰標記，而

${\varphi }_L$ 與

${\varphi }_R$ 可能被稱為 push，表示把標記往下一層推進。

二元索引樹

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

二元索引樹

${\tau }_x:T\to S$ 是啥？

當

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

${\tau }_x$：

Work In Progress…