Prefix (1..k):

Add to idx:Δ:

Overview & Concept

A Fenwick Tree (Binary Indexed Tree / BIT) is an exceptionally compact data structure that efficiently maintains prefix sums of a dynamic array of numbers. Invented by Peter Fenwick in 1994, it uses bitwise operations on two's complement binary representations (LSB = i & -i) to store cumulative sub-interval sums in a flat array of size n+1, executing both prefix sum queries and point updates in O(log n) time with zero pointer memory overhead.

How It Works

1-Based LSB Indexing: Each node at index i is responsible for the sub-interval [i - (i & -i) + 1 .. i].

LSB Isolation: The expression (i & -i) isolates the lowest set bit (the largest power of 2 dividing i).

Prefix Sum Peeling: To query prefix sum [1..i], accumulate tree[i] and peel off the lowest bit: i -= (i & -i) until i = 0.

Point Update Climbing: To add delta to array[i], add delta to tree[i] and advance to parent intervals: i += (i & -i) until i > n.

Step-by-Step Execution

1. Isolate LSBCompute lowest set bit via bitwise AND with two's complement negation: lsb = i & (-i).

2. Accumulate or ModifyFor query: add tree[i] to running sum. For update: add delta to tree[i].

3. Bitwise HopFor query: step down (i -= lsb). For update: step up (i += lsb).

4. Range QueryCompute range sum [L..R] as query(R) - query(L - 1).

Asymptotic Complexity Analysis

Metric	Best Case	Average Case	Worst Case	Space Complexity
Complexity Bound	O(log n) queries and updates	O(log n)	O(log n) bounded by number of set bits	O(n) exact compact buffer
Explanation	Optimal input arrangement minimizing operations.	Expected time for uniformly distributed randomized inputs.	Adversarial degenerate conditions requiring full traversal.	Auxiliary memory allocated beyond original input size.

Pseudocode & Invariants

Algorithm Logic

// Fenwick Tree / Binary Indexed Tree (BIT)
// Isolated LSB: i & (-i)

operation query(idx):
  sum = 0
  while idx > 0:
    sum += tree[idx]
    idx -= idx & (-idx) // Strip LSB
  return sum

operation update(idx, delta):
  while idx <= n:
    tree[idx] += delta
    idx += idx & (-idx) // Add LSB

operation rangeQuery(l, r):
  return query(r) - query(l - 1)

Algorithmic Invariants

Binary Power Invariant: The length of the interval covered by index i is exactly 2^k where k is the index of the lowest set bit in i.
Disjoint Covering Invariant: The path from index i to 0 visits a strictly disjoint partition of intervals summing to prefix(i).

Correctness Guarantee: Invariants hold true prior to loop entry, are preserved during every iteration, and guarantee correct post-condition upon termination.

Advantages & Disadvantages

Key Advantages

•Exact O(n) memory consumption with zero pointer overhead (a flat primitive array of size n+1).
•Extremely high CPU cache performance and minimal constant execution factor.
•Very concise code implementation (under 15 lines of code).

Trade-offs & Limitations

•Restricted to invertible group operations (such as addition, multiplication, XOR).
•Difficult to compute Range Minimum/Maximum queries without extensions.

Real-World Applications

Competitive Gaming Leaderboards

Maintaining real-time ranking and frequency distributions of millions of player scores.

Inversion Counting

Counting inverted pairs in an array in O(n log n) time during sorting and permutation analysis.

Data Compression (Arithmetic Coding)

Tracking adaptive cumulative symbol frequencies in statistical compression engines.

Decision Guide: When to Use

Ideal Scenarios

✓When calculating running prefix/range sums with frequent element modifications.
✓When memory efficiency and execution speed are paramount.

Consider Alternatives When

✕When operations are non-invertible (e.g. Range Minimum Query; use Segment Tree).

Compare trade-offs and complexity across complementary tools in AlgoViz.

Segment Tree Binary Search