【Fenwick_Tree編】AtCoder Library 解読 〜Pythonでの実装まで〜 - Qiita

を計算する必要があるので、計算量は $O(N)$ となります。 1.2. 部分和といえば累積和 クエリsumのような数列の部分和といえば累積和が思いつくでしょう。実際、数列 $a$ の累積和をとった配列を用意すればクエリsumは $O(1)$ で処理できます。 しかし、クエリaddはどうでしょうか。数列 $a$ の１箇所を変更すると累積和を計算し直す必要があるので結局、計算量は $O(N)$ となります。 1.3. そんなときにフェニック木 愚直解も累積和もadd,sum両方のクエリを処理するためには１回あたり計算量 $O(N)$ が必要でした。もちろんこれで間に合う場合はいいのですがもっと速くしたい。。。 そんなときに登場するのがフェニック木です。フェニック木はクエリadd, sumの両方を１回あたり $O(\log N)$ で処理できます！ フェニック木は Binary Indexed