Binary Indexed Tree の基礎と応用
概要
Binary Indexed Tree（BIT）は、単点更新と区間クエリを効率的に処理できるデータ構造です。計算量 O(log N) で操作を実行可能であり、競技プログラミングやアルゴリズム最適化で広く利用されます。
構造と原理
BIT は 2 進数表現に基づく構造を利用します。任意の整数は複数の 2 のべき乗和で表せることから、配列要素をべき乗区間で管理します。lowbit 演算（x & - ...
6月25日 18:51 投稿
AtCoder ABC389のアルゴリズム実装と解説
問題C: キューによる区間管理のシミュレーション
この問題では、列の先頭への追加や末尾からの削除、特定位置の要素へのアクセスを効率的に行う必要があります。全ての要素を個別に保持するとメモリや計算量が膨大になるため、連続する要素を「区間」として管理する手法をとります。
各区間について「先頭からの相対距離（開始位置）」と「区間の長さ」を構造体で定義し ...
6月6日 19:20 投稿