https://sci-hub.st/https://doi.org/10.1137/S0097539795291598
有一天我在 Backend TW 介紹一篇 LeetCode 答案的時候，多謝網友 Kakaen 介紹，其實早就該讀這篇論文了。這篇論文講得是 prefix sum 的 lower bound，lower bound 論文總是有趣的。
這篇論文要求的背景知識不少，這裡會佔很多的篇幅，會的話可以跳過，或者快速複習一下就可以了。
在 algorithm 的世界裡，我們一般講 upper bound，主要是想說明某個 algorithm 最多使用多少 resources。說明某個 algorithm 最少使用多少 resources 一般來說沒甚麼用，因為最快的 case 總是很快的，例如 input 是 null 就迅速結束，但那又如何呢？
所以在 algorithm 的世界裡，講 lower bound，是講問題的 lower bound，就是說，任何一個 algorithm 出 solve 某某的 problem 都必須花上的 resources。
難點當然是「任何」algorithm ⋯ 你怎麼知道所有的 algorithms？
如果我說我的 algorithm 是問神仙，可以極速完成，那你能說明我對還是錯嗎？最少有爭議性吧。所以我們需要 computational model 這個概念。Computational model 限制了可能的 algorithm。比如說一定要用電腦來算，又或者是說 sorting 必須只使用比較等等 ⋯
Semigroup 是一個抽象代數的 construction，它是一個 set $S$ 和一個我們叫做 $+$ 的 operation，符合這些 axiom
Closure: 對於任何的 $x, y \in S$，$x + y \in S$
Associativity: 對於任何的 $x, y, z \in S$，$(x + y) + z = x + (y + z)$