セグメント木（セグ木）とは何か　ポインタスーパー配列（私が名付けました）とは何か

数式は出て来ませんが、順序対という概念が出て来ます。
（編集が終わってからの追記）
と思ったけど、出て来ませんでした。
一応、セグメント木のデータは、自然数nとデータxの順序対
(n, x)で表せます。ですので出て来なかったというよりも、あえてそのように表さなかったということです。

セグメント木（セグ木）とは、完全n分木を用いたデータ構造です。
葉（末端の節）のみを用いるので、それ以外の余分な節の分メモリやストレージを食います。しかも、数学的にもコンピュータサイエンス的にも、1次元配列と全く同じデータ構造です。
しかし、目的のデータを読み込むスピードは、1次元配列がO(n)のデータでも、ほとんどO(1)、つまりn倍以上高速です。（もっと高速です。$n^m$個のデータを、$m$で読み込めるし、書き込みやアクセスもそれに準じます。
深さが1増えると、処理の命令が1つ増えると考えると、処理の速さは1次元配列の$n^{n^{n^n\cdots}}$倍です。）


仕組み

n分木なら実装できますが、人間に理解しやすいので$n=10$とします。
根は空白、葉は保存されたデータ、それ以外の全ての節に$0 \tilde{} 9$(または$1 \tilde{} 10)$の整数（以下この整数を添字と呼ぶ）を割り振ります。
1次元配列はnというデータの場所を読み込む際に、0から添字を1ずつ増やし、探索します。それに対して、セグメント木は添字の10進数を一番上の桁から探索し、1つの根または節から1つ下の節に降りていく際に、探索するデータの、残りの量が$1/10(1/n)$になります。
具体的に例を挙げます。
深さ5の完全10分木と、配列の添字が$0\tilde{}9999$まである1次元配列の場合を比較します。データの入っている場所は、7238番目の場所ということにします。
順番をあえて逆にして、まず1次元配列の場合。0から順番に添字を1ずつ増加させるので、ポインタ変数（カウンター）が7237回加算されます。一回加算するのに
1「クロック」掛かるとすると、
7237クロック掛かります。
それに対してセグメント木の場合、
根のすぐ下の10個の枝に
$0 \tilde{} 9$の添字が付いている場合「6」
$1 \tilde{} 10$の添字が付いている場合場所を表す非負整数の1桁目「7」の枝が選ばれます。
同様に「1」または「2」
「2」または「3」
「7」または「8」
の枝が順に選ばれます。全ての選択が済むと、1次元配列でポインタ変数（カウンター）を7237回増加させたのと同じように、目的のデータのある場所に到達できます。つまり4クロックしか掛かりません。その為非常に高速です。

遅延セグメント木

これは詳細は分かりませんが、データをソートしておけば万全です。
おそらくセグメント木のデータの保管場所に冗長性を持たせて、並列処理で適切に最適化する為のものでしょうが、データをサイズで昇順にソートしておけば、処理にどれほど時間が掛かるか、大体分かります。

ポインタスーパー配列

発案した当初は、
"super-form"
または
"flexible deque"
と呼んでいました。
仕組みは非常に簡単で、n行3列の2次元配列です。n個のデータを保存できます。
2列目は0から順番に自然数が入っています。
3列目は2列目の自然数のアドレスの入ったポインタ変数が入っています。
1列目にデータが入っています。
データの入れ替えをする時に、3列目のポインタ変数の指す自然数のアドレスを入れ替えます。
すると、3列目のポインタ変数の指している自然数が、データの入っている順番を表している状態が維持されるので、手続きに参照渡しで変数を渡したような意味になり、非常に高速です。
勿論順番が余りにも激しく変化したら、余剰のCPUパワーでソートする必要があります。
応用として、既存のソートされていないデータに同じようにポインタ変数を割り振れば、ソフト的にソートされているように扱えます。
これは便利ですね。


こうぼくん「セグメント木か」
たまねぎくん「便利だね」
かわぐちさん「のんびりしよう」
こうぼくん「うん」