Segment Tree and Fenwick
Five prompts on range-sum queries with point updates: segment tree shape, Fenwick (BIT) low-bit trick, comparison of the two, and a Fenwick bug hunt.
Question Bank
Hard
Python
segment-tree
fenwick-tree
range-queries
data-structures
677 views
3
Implement an iterative Fenwick tree (1-indexed) supporting update(i, delta) and prefix_sum(i). State the role of the low-bit operation.
Examples
Example 1:
Input: Fenwick of size 5; update(2, 5); update(4, 3); then prefix_sum(4) and range_sum(3, 4)
Output: prefix_sum(4) = 8; range_sum(3, 4) = 3
Explanation: update walks up via i += i & -i adding delta; prefix_sum walks down via i -= i & -i accumulating. range_sum(l, r) = prefix_sum(r) - prefix_sum(l - 1). Each op is O(log n).4 more questions, with full solutions and explanations, are available for premium members.
Upgrade to Premium