Fenwick tree - Algorithmist

Fenwick tree (aka Binary indexed tree) is a data structure that maintains a sequence of elements, and is able to compute cumulative sum of any range of consecutive elements in O(log⁡n) time. Changing value of any single element needs O(log⁡n) time as well. The structure is space-efficient in the sense that it needs the same amount of storage as just a simple array of n elements. The basic rule tha

[osamu0329]

任意の範囲の累積頻度がO(log(n))で計算できる。頻度の更新はO(log(n))。スペースはn配列と同程度

[sh19910711]

Binary Indexed Trees (BIT) C++による実装例