区間加算（区間に値を足す）と区間和（ある区間の合計を求める）という二種類の操作を両方高速に処理する実装として一般に使われる方法はどれか？ 2025.09.22 区間加算（区間に値を足す）と区間和（ある区間の合計を求める）という二種類の操作を両方高速に処理する実装として一般に使われる方法はどれか？ 単純配列での差分を都度再計算する Fenwick木（BIT）を2本用いる方法（差分テクニック） 遅延伝播のないセグメントツリー 二分探索木（平衡木）で値を管理する 区間加算と区間和の両方をO(log n)で処理する一つの方法はFenwick木を2本使う差分テクニックです。一方のBITで加算量の累積を、もう一方で位置に応じた係数を管理することで任意区間の和を求められます。遅延伝播付きセグメントツリーでも可能ですが、ここでの選択肢としては2本のBITが正答になります。 クイズタグ: 競技プログラミング関連記事 競技プログラミングクイズ！【問題 全10問・答え付き】 | 2025年09月版
