PyPyでの区間取得系データ構造の簡単な速度比較(競プロ文脈) - Qiita

こんにちは。株式会社オプティマインドの伊豆原と申します。当社の最適化チームに所属しており、また社内部活として競プロ部に所属してます。 競プロでは配列データ$[a_0,\cdots,a_{N-1}]$と2項演算$\oplus$が与えられた時に、連続部分列$[a_l,\cdots,a_{r-1}]$に対する$a_l \oplus a_{l+1} \oplus \cdots \oplus a_{r-1}$を高速に求めたいことがよくあります。こういった時は計算量$\mathcal{O}(\log N)$で求められるSegment TreeやBinary Indexed Tree、データの更新がなければSparse Table(こちらは$\mathcal{O}(1)$で求めれます)などがよく使われ、また一般に(ニーズが合えば)Segment TreeよりもBinary Indexed TreeやSp