Binary Indexed Tree (Fenwick Tree / BIT)
A BIT supports prefix sum queries and point updates in O(log n) time with O(n) space. Simpler to implement than a segment tree. Use when you only need prefix sums or range sums (not range min/max) and only point updates (not range updates). Key operations: update(i, delta) adds delta to index i. query(i) returns prefix sum [1..i]. range_query(l, r) = query(r) – query(l-1).
class BIT:
def __init__(self, n: int):
self.n = n
self.tree = [0] * (n + 1)
def update(self, i: int, delta: int):
while i int:
total = 0
while i > 0:
total += self.tree[i]
i -= i & (-i) # remove lowest set bit
return total
def range_query(self, l: int, r: int) -> int:
return self.query(r) - self.query(l - 1)
# Count of Smaller Numbers After Self (LC 315): coordinate compress, BIT
def count_smaller(nums: list[int]) -> list[int]:
sorted_unique = sorted(set(nums))
rank = {v: i+1 for i, v in enumerate(sorted_unique)}
bit = BIT(len(sorted_unique))
result = []
for n in reversed(nums):
result.append(bit.query(rank[n] - 1)) # count smaller elements
bit.update(rank[n], 1)
return result[::-1]Segment Tree – Range Queries and Point Updates
class SegmentTree:
def __init__(self, nums: list[int]):
self.n = len(nums)
self.tree = [0] * (4 * self.n)
self._build(nums, 0, 0, self.n - 1)
def _build(self, nums, node, start, end):
if start == end:
self.tree[node] = nums[start]
else:
mid = (start + end) // 2
self._build(nums, 2*node+1, start, mid)
self._build(nums, 2*node+2, mid+1, end)
self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]
def update(self, idx, val, node=0, start=0, end=None):
if end is None: end = self.n - 1
if start == end:
self.tree[node] = val
else:
mid = (start + end) // 2
if idx int:
if end is None: end = self.n - 1
if r < start or end < l:
return 0
if l <= start and end <= r:
return self.tree[node]
mid = (start + end) // 2
return (self.query(l, r, 2*node+1, start, mid) +
self.query(l, r, 2*node+2, mid+1, end))
# O(n) build, O(log n) update and queryLazy Propagation – Range Updates
# Range update (add val to all elements in [l, r]) + range sum query
class LazySegTree:
def __init__(self, n: int):
self.n = n
self.tree = [0] * (4 * n)
self.lazy = [0] * (4 * n)
def _push_down(self, node, start, end):
if self.lazy[node] != 0:
mid = (start + end) // 2
for child in [2*node+1, 2*node+2]:
size = (mid - start + 1) if child == 2*node+1 else (end - mid)
self.tree[child] += self.lazy[node] * size
self.lazy[child] += self.lazy[node]
self.lazy[node] = 0
def range_update(self, l, r, val, node=0, start=0, end=None):
if end is None: end = self.n - 1
if r < start or end < l: return
if l <= start and end int:
if end is None: end = self.n - 1
if r < start or end < l: return 0
if l <= start and end <= r: return self.tree[node]
self._push_down(node, start, end)
mid = (start + end) // 2
return (self.range_query(l, r, 2*node+1, start, mid) +
self.range_query(l, r, 2*node+2, mid+1, end))When to Use BIT vs Segment Tree
Use BIT (Fenwick Tree) when: point updates + prefix/range sum queries only. Simpler code, smaller constant factor, O(log n) both ops. Examples: count inversions, count smaller elements (LC 315), range sum query (LC 307). Use Segment Tree when: range min/max queries (not just sum), lazy range updates (add/set a value to a range), more complex aggregations (GCD, OR, AND over range). Segment tree is more general but more code. Use Lazy Segment Tree when: range updates (update all elements in [l,r]) + range queries. Without lazy propagation, range updates are O(n) per update. Lazy defers updates to save work. Interview tip: BIT is usually sufficient for sum problems. Jump to segment tree only if you need range min/max or range updates.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is a Fenwick Tree (BIT) and when should you use it over a segment tree?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A Fenwick Tree (Binary Indexed Tree, BIT) supports point updates and prefix sum queries in O(log n) time with O(n) space and very simple implementation. Use a BIT when: you only need sum aggregation (not min/max), you only have point updates (not range updates), and you want minimal code complexity. A segment tree is more general and supports range min/max queries and range updates with lazy propagation. For competitive programming sum problems, BIT is usually the right choice. For range min/max or range updates, use a segment tree.”}},{“@type”:”Question”,”name”:”How does the lowbit trick work in a Fenwick Tree?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”The lowbit of i is i & (-i), which isolates the lowest set bit of i. In a BIT: update(i) propagates changes upward by adding lowbit(i) to i on each iteration. query(i) computes prefix sums by subtracting lowbit(i) from i on each iteration. This creates a tree structure where each index i is responsible for a range of size lowbit(i). Both operations run in O(log n) because each step changes the number of set bits in i.”}},{“@type”:”Question”,”name”:”How does lazy propagation work in a segment tree?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Lazy propagation defers range updates: instead of immediately updating all O(n) leaf nodes in a range, store a pending update in the lazy array at the node covering the range. When you later query or update a child of that node, push the lazy value down (propagate to children and clear from parent). This amortizes the cost: a range update that would cost O(n) without lazy takes O(log n) with lazy, because you only update O(log n) segment tree nodes. Push-down must happen before accessing any child node.”}},{“@type”:”Question”,”name”:”How do you use a segment tree for range minimum queries?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Build the segment tree with the merge operation returning min instead of sum: tree[node] = min(tree[2*node+1], tree[2*node+2]). Point update: update the leaf and propagate min up. Range min query: return min of left and right child queries when the range partially overlaps. The identity value for out-of-range nodes is infinity instead of 0. Range minimum queries are the standard use case where BIT cannot be used (BIT only supports invertible operations like sum).”}},{“@type”:”Question”,”name”:”How do you solve the "count of smaller numbers after self" problem with a BIT?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Coordinate compress the input values to ranks 1..k. Traverse the array right to left. For each element at rank r: query the BIT for prefix sum up to rank r-1 (count of elements already inserted with smaller rank = smaller value). Then update the BIT at rank r. Since we traverse right to left, all queried elements are to the right of the current element. The BIT gives prefix counts in O(log k) per element, total O(n log n). This is LC 315 (Count of Smaller Numbers After Self).”}}]}
Meta coding interviews include advanced data structure problems with range queries. See typical problems at Meta interview: segment tree and range query problems.
Databricks interviews test range query and aggregation data structures. Review patterns for Databricks interview: range queries and stream aggregation.
Atlassian coding rounds include advanced data structure problems. See common patterns for Atlassian interview: advanced data structure problems.