58. Fenwick Tree (BIT)

Hard

Topics

Helpful tools to learn & understand

Visualize LogicActive Simulator

Watch key transitions, pointers, and variables update step-by-step.

Open

Check Solutions

Read clean, documented implementations across multiple patterns.

View Code

Thinkpad (Draw & Note)

Sketch diagrams on an infinite canvas and draft notes directly inline.

Draw

Example 1:

Input: nums = [3, 2, -1, 6, 5, 4, -3, 3, 7, 2, 3]

Output:

Prefix Sum up to index 5: 19 (3 + 2 + (-1) + 6 + 5 + 4 = 19), After updating nums[2] to 5: New Prefix Sum up to index 5: 25 (3 + 2 + 5 + 6 + 5 + 4 = 25)

Explanation: This demonstrates the initial calculation of a prefix sum and then the effect of an update on a subsequent prefix sum calculation.

Example 2:

Input: nums = [1, 2, 3, 4, 5]

Output: Prefix Sum up to index 3: 10 (1+2+3+4), After updating nums[1] to 5: New Prefix Sum up to index 3: 13 (1+5+3+4)

Explanation: Shows the impact of updating an element on subsequent prefix sum queries.

Constraints:

•
•
•

Time Complexity

O(log n)

Space Complexity

O(n)