Log inSign up
mediumGeeksforGeeksNot Started

Fenwick Tree / Binary Indexed Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Advanced DSA
Solve on GeeksforGeeks
Lesson

Problem Statement

A Fenwick Tree (or Binary Indexed Tree) is a data structure providing efficient methods for calculation and manipulation of prefix sums of a table of values.

Given an array of integers nums of size n, implement a FenwickTree supporting: 1. update(index, delta): Adds delta to the element at the 1-based index. 2. query(index): Computes the prefix sum of elements from index 1 to index. 3. queryRange(left, right): Computes the range sum of elements from index left to right (1-based, inclusive).

Both update and query must run in O(log n) time using bitwise manipulation (i & -i).

Example 1 · Example 1:

Input: nums = [2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9] operations: [query(5), update(3, 6), query(5), queryRange(2, 6)]
Output: [9, null, 15, 18]
Explanation: Prefix sum of first 5 elements [2, 1, 1, 3, 2] = 9. After update(3, 6), nums[3] changes from 1 to 7. New prefix sum of first 5 elements = 15. Range sum from index 2 to 6 = nums[2] + nums[3] + nums[4] + nums[5] + nums[6] = 1 + 7 + 3 + 2 + 5 = 18.

Example 2 · Example 2:

Input: nums = [1, 2, 3, 4, 5] operations: [queryRange(1, 5), update(1, 10), queryRange(1, 5)]
Output: [15, null, 25]
Explanation: Sum of 1..5 is 15. After adding 10 to index 1, sum is 25.

Constraints:

  • 1 <= n <= 105
  • -104 <= nums[i], delta <= 104
  • 1 <= left <= right <= n

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 3 distinct approaches for Fenwick Tree (Binary Indexed Tree).
  • Implement fully runnable solutions in C++, Java, Python, and JavaScript.
  • Analyze algorithmic trade-offs across data structure designs.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Fenwick Tree (Binary Indexed Tree)
  • Advanced Data Structures & Algorithmic Paradigm
  • Fast Range Queries or Amortized Dynamic Operations

Algorithmic Decision Tree:

  • BRUTE_FORCE: When queries are extremely rare compared to updates.
  • BETTER: When queries heavily dominate updates.
  • OPTIMAL: The standard optimal implementation for dynamic prefix and range sum queries with point updates.

Connected Patterns:

Segment TreeFenwick TreeDisjoint Set UnionDesign Data Structures

1. Raw Array Storage

Intuition

Store the input array in standard 1-based indexed memory: - update(index, delta): Modify the single element nums[index] += delta in O(1). - query(index): Loop from 1 to index accumulating sum in O(n). - queryRange(left, right): Loop from left to right summing elements in O(n). Processing Q queries on an array of length N takes O(Q \cdot N) worst case.

When to apply: When queries are extremely rare compared to updates.

Algorithm

  1. Step 1: Store elements in an array nums of size n + 1.
  2. Step 2: On update(index, delta), nums[index] += delta in O(1).
  3. Step 3: On query(index), loop i from 1 to index adding nums[i].
  4. Step 4: On queryRange(left, right), loop i from left to right adding nums[i].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class FenwickBrute {
5 std::vector<int> nums;
6public:
7 FenwickBrute(const std::vector<int>& arr) {
8 nums.resize(arr.size() + 1, 0);
9 for (size_t i = 0; i < arr.size(); ++i) nums[i + 1] = arr[i];
10 }
11 void update(int idx, int delta) {
12 nums[idx] += delta;
13 }
14 long long query(int idx) {
15 long long sum = 0;
16 for (int i = 1; i <= idx; ++i) sum += nums[i];
17 return sum;
18 }
19 long long queryRange(int l, int r) {
20 long long sum = 0;
21 for (int i = l; i <= r; ++i) sum += nums[i];
22 return sum;
23 }
24};
25
26int main() {
27 std::vector<int> nums = {2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9};
28 FenwickBrute ft(nums);
29 std::cout << ft.query(5) << std::endl;
30 ft.update(3, 6);
31 std::cout << ft.query(5) << std::endl;
32 std::cout << ft.queryRange(2, 6) << std::endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(1) for update, O(n) for query and queryRange
  • Space complexity: O(n) auxiliary space

2. Prefix Sum Array with Recomputation

Intuition

Store prefix sums: pref[i] = nums[1] + ... + nums[i]. - query(index): Returns pref[index] in O(1). - queryRange(left, right): Returns pref[right] - pref[left - 1] in O(1). - update(index, delta): Every prefix sum from index to n must be updated: \text{pref}[k] += delta for k \in [index, n]. This requires O(n) time. While queries are instant, frequent updates degrade performance to O(n) each.

When to apply: When queries heavily dominate updates.

Algorithm

  1. Step 1: Compute prefix sum array pref of size n + 1.
  2. Step 2: On query(index), return pref[index] in O(1).
  3. Step 3: On queryRange(l, r), return pref[r] - pref[l - 1] in O(1).
  4. Step 4: On update(index, delta), loop i from index to n adding delta to pref[i] in O(n).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class FenwickPrefix {
5 int n;
6 std::vector<long long> pref;
7public:
8 FenwickPrefix(const std::vector<int>& arr) : n(arr.size()), pref(arr.size() + 1, 0) {
9 for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] + arr[i];
10 }
11 void update(int idx, int delta) {
12 for (int i = idx; i <= n; ++i) pref[i] += delta;
13 }
14 long long query(int idx) {
15 return pref[idx];
16 }
17 long long queryRange(int l, int r) {
18 return pref[r] - pref[l - 1];
19 }
20};
21
22int main() {
23 std::vector<int> nums = {2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9};
24 FenwickPrefix ft(nums);
25 std::cout << ft.query(5) << std::endl;
26 ft.update(3, 6);
27 std::cout << ft.query(5) << std::endl;
28 std::cout << ft.queryRange(2, 6) << std::endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(n) for update, O(1) for query and queryRange
  • Space complexity: O(n) space for prefix array

3. Binary Indexed Tree (Fenwick Tree)

Intuition

A Fenwick tree stores partial sums such that each index i is responsible for 2^{\text{LSB}(i)} = (i \mathrel{\&} -i) elements: 1. Prefix Sum: - To compute \sum_{k=1}^i \text{nums}[k], add \text{tree}[i] and transition to i - (i \mathrel{\&} -i) (stripping the lowest set bit). - Repeats at most \lfloor \log_2 n \rfloor times -> O(log n). 2. Point Update: - Adding \delta to \text{nums}[i] affects all indices whose responsibility ranges cover i. - Start at i, add \delta to \text{tree}[i], and transition to i + (i \mathrel{\&} -i) (adding the lowest set bit). - Repeats at most \lfloor \log_2 n \rfloor times -> O(log n). 3. Range Sum: - \text{queryRange}(l, r) = \text{query}(r) - \text{query}(l - 1) in O(log n). 4. Linear Time Construction: - A tree can be built in O(n) time by pushing \text{tree}[i] into its parent i + (i \mathrel{\&} -i).

When to apply: The standard optimal implementation for dynamic prefix and range sum queries with point updates.

Algorithm

  1. Step 1: Allocate tree array of size n + 1.
  2. Step 2: Linear construction in O(n): copy arr into tree[1..n], then for each i, add tree[i] to tree[i + (i & -i)] if within bounds.
  3. Step 3: On update(idx, delta): while idx <= n, tree[idx] += delta, idx += idx & -idx.
  4. Step 4: On query(idx): sum = 0; while idx > 0, sum += tree[idx], idx -= idx & -idx; return sum.
  5. Step 5: On queryRange(l, r): return query(r) - query(l - 1).

Interactive trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
query(5): Start at index 5 (binary 101)
Visual state
Values and pointers at this exact step
pointers
S
2
1
1
3
2
0
1
2
3
4
↑ nextIdx
Check / comparison
Indices visited: 5, 4
Decision / next transition
query(5) = 9
Why this step matters

query(5): Start at index 5 (binary 101). Add tree[5]. Step: 5 - (5 & -5) = 4 (binary 100). Add tree[4]. Step: 4 - 4 = 0. Total sum = 9.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class FenwickTree {
5 int n;
6 std::vector<long long> tree;
7public:
8 FenwickTree(const std::vector<int>& arr) : n(arr.size()), tree(arr.size() + 1, 0) {
9 for (int i = 0; i < n; ++i) tree[i + 1] = arr[i];
10 // O(n) construction
11 for (int i = 1; i <= n; ++i) {
12 int parent = i + (i & -i);
13 if (parent <= n) tree[parent] += tree[i];
14 }
15 }
16
17 void update(int idx, int delta) {
18 for (; idx <= n; idx += idx & -idx) {
19 tree[idx] += delta;
20 }
21 }
22
23 long long query(int idx) {
24 long long sum = 0;
25 for (; idx > 0; idx -= idx & -idx) {
26 sum += tree[idx];
27 }
28 return sum;
29 }
30
31 long long queryRange(int l, int r) {
32 if (l > r) return 0;
33 return query(r) - query(l - 1);
34 }
35};
36
37int main() {
38 std::vector<int> nums = {2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9};
39 FenwickTree ft(nums);
40 std::cout << ft.query(5) << std::endl;
41 ft.update(3, 6);
42 std::cout << ft.query(5) << std::endl;
43 std::cout << ft.queryRange(2, 6) << std::endl;
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(n) construction, O(log n) for update, query, and queryRange
  • Space complexity: O(n) auxiliary space for the tree array

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Raw Array StorageO(1) for update, O(n) for query and queryRangeO(n) auxiliary spaceStore items in an array. Point updates run in O(1), but range/prefix queries require O(n) loops.O(1) for update, O(n) for query and queryRange
2.Prefix Sum Array with RecomputationO(n) for update, O(1) for query and queryRangeO(n) space for prefix arrayMaintain a prefix sum array. Prefix and range queries take O(1), but updates require updating all subsequent prefix sums in O(n).O(n) for update, O(1) for query and queryRange
3.Binary Indexed Tree (Fenwick Tree)OptimalO(n) construction, O(log n) for update, query, and queryRangeO(n) auxiliary space for the tree arrayStore partial sums where index i stores sum of range (i - (i & -i), i]. Execute both updates and queries in O(log n) time using lowest set bit manipulation.O(n) construction, O(log n) for update, query, and queryRange

Common Pitfalls & Crucial Edge Cases

Using 0-based indexing without offset

Triggers an immediate infinite loop on index 0.

Confusing Fenwick Tree with Segment Tree memory

Fenwick Tree requires only O(N) space (exactly N elements), whereas Segment Tree requires 4N space.

Attempting arbitrary range min/max updates without extra constraints

Standard Fenwick Tree only supports invertible operations (like sum and XOR). For general range min/max with point updates, a Segment Tree is preferred.

Crucial Edge Cases to Validate:

  • Index 0 input — Must add 1 to index (i + 1) to convert 0-based client inputs to 1-based Fenwick Tree.
  • Range query with L == 1 — query(R) - query(0) = query(R).
  • Delta is negative (subtraction) — Handled cleanly by addition of negative delta.
  • Tree size N — Loop in update terminates when i > N.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Draw the binary index interval diagram: show how 1 covers 1, 2 covers 2, 4 covers 4, 8 covers 8.
  2. Contrast Fenwick Tree with Segment Tree: Fenwick has lower constant factor, uses 4x less memory, and is much faster to code.
  3. Explain the lowbit trick i & -i and its derivation from two's complement arithmetic.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What does the lowbit operation i & -i compute in a Fenwick Tree?

2.How do you navigate during a point update add(i, delta) vs a prefix query query(i)?

3.Why must Fenwick Trees strictly use 1-based indexing?

Back to DSA Sheet