RootishArrayStack

Array Stackとかを複数使う。いや配列だったらいいんだけど。たぶん

具体的には、いつもだと

■■■■■■■■■□□□□□□

としているところを

■ ■■ ■■■ ■■■□ □□□□□

のように、5つの配列で表す。

具体的には、配列をr個用意して、0,1,2...r-1と番号をつける。i番目の配列のサイズはi+1にする。左から詰めて配置していく。

満タンになったら1配列追加。逆に2つ配列が余ったら一番右の配列を消して余り配列を1つにする。

■ ■■ ■■■ □□□□ □□□□□

■ ■■ ■■■ □□□□

みたいな。

resize()の代わりにgrow()とshrink()を使う。配列を増やしたり減らしたり。要素のコピーが発生しないし、r個目の配列(横幅r)を追加するのにO(r)かかったとしても、結局add/removeする回数もr回くらいになる(growとgrowの間に行われるaddの回数を考えるとわかる)ので、償却されてO(1)になる。

無駄な領域の大きさもO(√n)で優秀。詳しくはp.47辺りを読めばいいけど、たとえば配列を□ □ □ みたいに1つずつ取ったとすると、無駄な領域は0…になるかと思いきや、それぞれの配列を指し示すポインタがn個必要になって、無駄が発生する。このポインタの数の無駄さと新しく配列を追加したよ！というときの無駄空間の良いラインを取ってるのがRootishArrayStack。すごい。

平方根の計算方法、わからん！ｗ （飛ばします…）