data-structures

双スタックスライディングウィンドウ集約

スライディングウィンドウ集約は通常、演算子が「可逆」であることを要求するため、最小値、分位数、さらには浮動小数点の合計さえも排除されてしまう。二スタック法は約二十行のコードで、結合法則を満たすあらゆる集約を償却O(1)で実現し、しかも結果はウィンドウ外の値に汚染されない。