Home/Questions/Q 3535
Next
In Process

RTSALL Latest Articles

Abhishek
Begginer
Asked: 2026-09-11T09:53:23-05:00 In: ,

How does a Fenwick Tree (Binary Indexed Tree) query and update prefix sums in O(log N) using i & (-i)?

We need dynamic prefix sums and range sum queries over a stream of financial ledger transactions where numbers are constantly updated.

A standard array has O(1) update but O(N) range sum. A prefix sum array has O(1) range sum but O(N) update. Segment trees solve both in O(log N) but require 4N memory and complex pointer/tree logic. Peter Fenwick’s Binary Indexed Tree (BIT) solves both in O(log N) with zero tree nodes and only 1N memory using the bit trick i & (-i). How does this lowbit navigation work?

Leave an answer

You must login to add an answer.

Need An Account,

2 Answers

  1. Anonymous
    Begginer

    Here is the clean C++20 Fenwick Tree (BIT) implementation. It uses int64_t for precision and i & (-i) for logarithmic index jumps.

    Modern C++20 Solution (Fully Runnable)

    #include <iostream>
#include <vector>
#include <cstdint>

class FenwickTree {
    int n;
    std::vector<int64_t> tree;

    static inline int lowbit(int x) noexcept {
        return x & (-x);
    }

public:
    FenwickTree(int size) : n(size), tree(size + 1, 0) {}

    void add(int i, int64_t delta) {
        for (; i <= n; i += lowbit(i)) {
            tree[i] += delta;
        }
    }

    int64_t queryPrefix(int i) const {
        int64_t sum = 0;
        for (; i > 0; i -= lowbit(i)) {
            sum += tree[i];
        }
        return sum;
    }

    int64_t queryRange(int l, int r) const {
        if (l > r) return 0;
        return queryPrefix(r) - queryPrefix(l - 1);
    }
};

int main() {
    FenwickTree bit(10);
    bit.add(1, 5);
    bit.add(2, 3);
    bit.add(3, 7);
    bit.add(4, 2);

    std::cout << "Prefix sum [1..3]: " << bit.queryPrefix(3) << "n";  // 15
    std::cout << "Range sum [2..4]:  " << bit.queryRange(2, 4) << "n"; // 12
    return 0;
}

    Complexity: O(log N) updates and queries with strictly 1N memory footprint.

    • 0
  2. Abhay Tiwari
    Begginer

    The Fenwick Tree (invented by Peter Fenwick in 1994) is one of the most compact data structures ever devised. It gives you the full power of a dynamic segment tree in just one flat array of size N with 10 lines of code.

    1. The Secret: Powers of 2 Range Decomposition

    Any positive integer can be uniquely represented as a sum of powers of 2. For example: 13 = 8 + 4 + 1.

    Fenwick took this idea and applied it to prefix ranges: instead of storing every single element, tree[i] stores the sum of a contiguous range of length equal to its lowest set bit!

    The length of the range responsible by index i is given by: lowbit(i) = i & (-i).

    • If i = 12 (1100_2): lowbit(12) = 4. So tree[12] stores the sum of 4 elements: indices [9, 10, 11, 12]!
    • If i = 8 (1000_2): lowbit(8) = 8. So tree[8] stores the sum of the first 8 elements: [1 ... 8]!

    2. The Two Operations

    A. Prefix Sum Query: `i -= (i & -i)`

    To calculate the prefix sum up to index 13:

    1. Read tree[13] (covers index 13). 13 - lowbit(13) = 13 - 1 = 12.
    2. Read tree[12] (covers indices 9 through 12). 12 - lowbit(12) = 12 - 4 = 8.
    3. Read tree[8] (covers indices 1 through 8). 8 - lowbit(8) = 8 - 8 = 0 (Done!).

    Total reads: only 3 steps to sum 13 numbers! At each step, you strip off one binary bit, taking at most O(log N) operations.

    B. Point Update: `i += (i & -i)`

    When you add delta to element i, which parent ranges need to be updated? Every index whose range covers i! You navigate up the tree simply by adding the lowest set bit: i += (i & -i)!

    Clean C++20 Implementation

    #include <vector>
#include <cstdint>

class FenwickTree {
    std::vector<int64_t> tree;
    int n;

    static inline int lowbit(int x) {
        return x & (-x);
    }

public:
    FenwickTree(int size) : n(size), tree(size + 1, 0) {}

    // Adds delta to index i (1-indexed) in O(log N)
    void update(int i, int64_t delta) {
        while (i <= n) {
            tree[i] += delta;
            i += lowbit(i);
        }
    }

    // Computes sum of prefix [1 ... i] in O(log N)
    int64_t query(int i) const {
        int64_t sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= lowbit(i);
        }
        return sum;
    }

    // Computes range sum [l ... r] in O(log N)
    int64_t queryRange(int l, int r) const {
        if (l > r) return 0;
        return query(r) - query(l - 1);
    }
};

    Why Fenwick Beats Segment Trees in Production

    MetricSegment TreeFenwick Tree
    Memory Overhead4N (or 2N)Strictly 1N (4x smaller)
    Implementation Size50-80 lines15 lines
    L1 Cache PerformanceModerateBlazing Fast (flat contiguous array)
    • 0