2020年3月5日データ構造データ構造,RAQ,RSQ,転倒数,二次元BIT,BIT,区間和,競プロ,二分探索,セグメント木

Binary Indexed Tree (またはフェニック木) は 数列 \(a_1, a_2, a_3, \cdots, a_n\) が与えられた時に、以下のようなことがそれぞれ \(O(log n)\) で実現できるデータ構造のこ ...

2020年2月27日データ構造データ構造,RAQ,二分探索,RSQ,セグメント木,二分木,完全二分木,区間,モノイド,更新

セグメント木とは

セグメント木とは、完全二分木（全ての葉の深さが等しい木）によって実装された、区間を扱うのに適したデータ構造のことです。

区間に対する操作を対数時間 O(log n) で行えることが特徴で、競技プログラミング ...