What is the time complexity of fenwick tree (bit)?

Worst case O(log n). Space complexity is O(n). Each step strips or adds one set bit, so at most log n iterations.

Fenwick tree (BIT)

hard

Node i covers the last (i & −i) elements ending at i - the binary representation of the index *is* the range decomposition. Half the code and half the memory of a segment tree.

Worst O(log n)Space O(n)

Loading the fenwick tree (bit) engine…

Where to go next

Segment tree

hard

Range queries and point updates, both O(log n).

Prefix sums

easy

Precompute once, answer every range query in O(1).

Bit manipulation playground

medium

Set, clear, toggle - and the two identities worth memorising.