ReslandSegment Trees & Fenwick Trees
Answer range queries on an array that keeps changing, with updates and queries both O(log n) instead of one of them costing O(n).
AdvancedRead first: Prefix Sums, Binary Trees
How It Works
A prefix sum array answers any range sum in O(1), but changing one element shifts every prefix after it, so an update costs O(n). A plain array has the opposite trade: O(1) updates, O(n) sums. When a problem mixes updates and queries, both structures here meet in the middle. Each stores the sums of carefully chosen blocks, so a query adds up O(log n) blocks and an update touches O(log n) blocks.
A segment tree is a binary tree over index ranges. The root covers the whole array, each node splits its range in half between its two children, and each leaf is a single element. Every node stores the sum (or min, max, gcd) of its range. Any query range breaks into O(log n) whole nodes, so the answer is a handful of stored values instead of a scan.
|----------------- 39 ------------------|
|------- 22 --------|------- 17 --------|
|-- 13 ---|--- 9 ---|--- 9 ---|--- 8 ---|
value 5 8 6 3 2 7 2 6
index 0 1 2 3 4 5 6 7A Segment Tree Query and Update
Step 1 of 14
tree
- Node handling the call now
- Passes the call down to its children
- Answered from its stored sum, or updated
- No overlap: skipped
Each node stores the sum of the range under it, and the leaves are the values themselves. To answer sumRange(2, 5), start at the root and ask how each node's range overlaps [2,5].
All 14 steps as text
- Each node stores the sum of the range under it, and the leaves are the values themselves. To answer
sumRange(2, 5), start at the root and ask how each node's range overlaps[2,5]. [0,7]only partly overlaps[2,5], so split the question between its halves,[0,3]and[4,7], and add their answers.[0,3]only partly overlaps[2,5], so split the question between its halves,[0,1]and[2,3], and add their answers.[0,1]doesn't overlap[2,5]at all, so it adds nothing. Return0without looking below it.[2,3]is fully inside[2,5], so return its stored sum,9, without visiting the 2 values under it. That's the speedup.[4,7]only partly overlaps[2,5], so split the question between its halves,[4,5]and[6,7], and add their answers.[4,5]is fully inside[2,5], so return its stored sum,9, without visiting the 2 values under it. That's the speedup.[6,7]doesn't overlap[2,5]at all, so it adds nothing. Return0without looking below it.sumRange(2, 5)returns9 + 9 = 18. Two stored sums answered it, and it never touched a leaf.update(3, 10)walks down[0,7],[0,3],[2,3],[3,3], always into the half that holds index3. At the leaf it sets3to10.- Back up at
[2,3], recompute the sum from its children:6 + 10 = 16. - Back up at
[0,3], recompute the sum from its children:13 + 16 = 29. - Back up at
[0,7], recompute the sum from its children:29 + 17 = 46. That's one node per level, so the update is O(log n). sumRange(2, 5)asks the same nodes as before and now gets16 + 9 = 25. The update fixed every stored sum that covers index3, so none of them went stale.
A Fenwick tree (also called a binary indexed tree) is the leaner cousin: one array of n + 1 numbers in which slot i holds the sum of a block that ends at i, sized by the lowest set bit of i. It only answers prefix sums, and gets a range sum by subtracting one prefix from another. The template shows how i & -i drives it.
- Pick a Fenwick tree when the operation can be undone (subtraction undoes a sum or a count, XOR undoes XOR) and you need point updates with prefix or range queries. It's about ten lines of code and n + 1 integers.
- Pick a segment tree when the operation can't be undone, like range min, max or gcd, since a prefix minimum can't be subtracted away. It also handles updates to a whole range (with lazy propagation) and nodes that merge something richer than a number, such as the best subarray inside their range.
- Both cost O(log n) per update and per query. The Fenwick tree has smaller constants and less to get wrong; the segment tree is the more general tool.
When to Reach for It
- An array gets point updates mixed in with range queries (sum, min, max, count).
- You'd reach for a prefix sum array, except the values change between queries.
- You process items in order and keep asking how many earlier ones are smaller or larger than the current one, as in counting inversions.
- Values are huge or negative, but only their relative order matters, so ranks will do.
- Both n and the number of queries are around 10^5, so O(n) per query is too slow.
Complexity
| Operation | Time | Space |
|---|---|---|
| Fenwick: point add or prefix sum | O(log n) | O(n) |
| Fenwick: range sum (two prefix sums) | O(log n) | O(n) |
| Segment tree: build | O(n) | O(n): 4n slots |
| Segment tree: point update or range query | O(log n) | O(log n) recursion |
| Plain prefix sum array, for comparison | O(1) query, O(n) update | O(n) |
The Template
A Fenwick Tree
Number the positions from 1 (the code takes 0-based indices and adds one on the way in). Slot i of tree holds the sum of the i & -i positions that end at i. Odd slots hold a single value, and slots with more trailing zeros hold longer runs, nested like the tick marks on a ruler.
i binary i & -i tree[i] sums positions
1 0001 1 1
2 0010 2 1..2
3 0011 1 3
4 0100 4 1..4
5 0101 1 5
6 0110 2 5..6
7 0111 1 7
8 1000 8 1..8
sum of 1..7: 7 -> 6 -> 4 -> 0
tree[7] + tree[6] + tree[4]
covers 7, 5..6 and 1..4
add at 3: 3 -> 4 -> 8
the only blocks that contain 3Why `i & -i` is the lowest set bit. Computers store -i in two's complement, which is ~i + 1: flip every bit, then add one. Flipping turns the trailing zeros of i into ones, and the + 1 carries through all of them until it lands on the first zero, which is exactly where i had its lowest 1. Below that spot both numbers are 0, and above it every bit is opposite. So the AND keeps that one bit and nothing else.
i = 0 1 1 0 0 12
~i = 1 0 0 1 1 every bit flipped
-i = 1 0 1 0 0 ~i + 1 (two's complement)
i & -i = 0 0 1 0 0 4, the lowest set bitprefixSum starts at i and keeps subtracting the lowest set bit, collecting one block per step until it reaches 0. Each step clears a bit, so it runs at most about log n times. add goes the other way: adding the lowest set bit jumps to the next, bigger block that also contains the position, until it falls off the end of the array. rangeSum(left, right) is prefixSum(right) - prefixSum(left - 1), the same trick as a plain prefix sum array.
Time O(log n) per add, prefix sum or range sumSpace O(n)
class FenwickTree:
"""Prefix sums over an array that changes. Positions are 1-indexed inside:
tree[i] holds the sum of the (i & -i) values that end at position i."""
def __init__(self, n: int) -> None:
# Slot 0 stays unused: 0 & -0 is 0, so the loops would never move.
self.tree = [0] * (n + 1)
def add(self, i: int, delta: int) -> None:
"""Add `delta` to nums[i]."""
i += 1 # Shift to 1-indexed.
while i < len(self.tree):
self.tree[i] += delta
i += i & -i # Climb to the next block that also covers this position.
def prefix_sum(self, i: int) -> int:
"""Sum of nums[0..i], inclusive."""
i += 1
total = 0
while i > 0:
total += self.tree[i]
i -= i & -i # Drop the lowest set bit: jump to the block just before this one.
return total
def range_sum(self, left: int, right: int) -> int:
"""Sum of nums[left..right], inclusive."""
return self.prefix_sum(right) - self.prefix_sum(left - 1)
if __name__ == "__main__":
nums = [3, 2, -1, 6, 5, 4, -3, 3]
tree = FenwickTree(len(nums))
for i, num in enumerate(nums):
tree.add(i, num)
print(tree.prefix_sum(4)) # 15
print(tree.range_sum(2, 5)) # 14
tree.add(3, 4) # nums[3] goes from 6 to 10.
print(tree.range_sum(2, 5)) # 18
print(tree.range_sum(0, 7)) # 23
print(tree.range_sum(6, 6)) # -3// Prefix sums over an array that changes. Positions are 1-indexed inside:
// tree[i] holds the sum of the (i & -i) values that end at position i.
export class FenwickTree {
private tree: number[];
constructor(n: number) {
// Slot 0 stays unused: 0 & -0 is 0, so the loops would never move.
this.tree = new Array<number>(n + 1).fill(0);
}
// Add `delta` to nums[i].
add(i: number, delta: number): void {
i++; // Shift to 1-indexed.
while (i < this.tree.length) {
this.tree[i] += delta;
i += i & -i; // Climb to the next block that also covers this position.
}
}
// Sum of nums[0..i], inclusive.
prefixSum(i: number): number {
i++;
let total = 0;
while (i > 0) {
total += this.tree[i];
i -= i & -i; // Drop the lowest set bit: jump to the block just before this one.
}
return total;
}
// Sum of nums[left..right], inclusive.
rangeSum(left: number, right: number): number {
return this.prefixSum(right) - this.prefixSum(left - 1);
}
}
const nums = [3, 2, -1, 6, 5, 4, -3, 3];
const tree = new FenwickTree(nums.length);
nums.forEach((num, i) => tree.add(i, num));
console.log(tree.prefixSum(4)); // 15
console.log(tree.rangeSum(2, 5)); // 14
tree.add(3, 4); // nums[3] goes from 6 to 10.
console.log(tree.rangeSum(2, 5)); // 18
console.log(tree.rangeSum(0, 7)); // 23
console.log(tree.rangeSum(6, 6)); // -3package main
import "fmt"
// fenwickTree keeps prefix sums over an array that changes. Positions are
// 1-indexed inside: tree[i] holds the sum of the (i & -i) values that end at
// position i.
type fenwickTree struct {
tree []int
}
func newFenwickTree(n int) *fenwickTree {
// Slot 0 stays unused: 0 & -0 is 0, so the loops would never move.
return &fenwickTree{tree: make([]int, n+1)}
}
// add adds delta to nums[i].
func (f *fenwickTree) add(i, delta int) {
i++ // Shift to 1-indexed.
for i < len(f.tree) {
f.tree[i] += delta
i += i & -i // Climb to the next block that also covers this position.
}
}
// prefixSum returns the sum of nums[0..i], inclusive.
func (f *fenwickTree) prefixSum(i int) int {
i++
total := 0
for i > 0 {
total += f.tree[i]
i -= i & -i // Drop the lowest set bit: jump to the block just before this one.
}
return total
}
// rangeSum returns the sum of nums[left..right], inclusive.
func (f *fenwickTree) rangeSum(left, right int) int {
return f.prefixSum(right) - f.prefixSum(left-1)
}
func main() {
nums := []int{3, 2, -1, 6, 5, 4, -3, 3}
tree := newFenwickTree(len(nums))
for i, num := range nums {
tree.add(i, num)
}
fmt.Println(tree.prefixSum(4)) // 15
fmt.Println(tree.rangeSum(2, 5)) // 14
tree.add(3, 4) // nums[3] goes from 6 to 10.
fmt.Println(tree.rangeSum(2, 5)) // 18
fmt.Println(tree.rangeSum(0, 7)) // 23
fmt.Println(tree.rangeSum(6, 6)) // -3
}using System;
public class Solution
{
// Prefix sums over an array that changes. Positions are 1-indexed inside:
// tree[i] holds the sum of the (i & -i) values that end at position i.
public class FenwickTree
{
readonly int[] tree;
public FenwickTree(int n)
{
// Slot 0 stays unused: 0 & -0 is 0, so the loops would never move.
tree = new int[n + 1];
}
// Add delta to nums[i].
public void Add(int i, int delta)
{
i++; // Shift to 1-indexed.
while (i < tree.Length)
{
tree[i] += delta;
i += i & -i; // Climb to the next block that also covers this position.
}
}
// Sum of nums[0..i], inclusive.
public int PrefixSum(int i)
{
i++;
int total = 0;
while (i > 0)
{
total += tree[i];
i -= i & -i; // Drop the lowest set bit: jump to the block just before this one.
}
return total;
}
// Sum of nums[left..right], inclusive.
public int RangeSum(int left, int right) => PrefixSum(right) - PrefixSum(left - 1);
}
public static void Main()
{
int[] nums = { 3, 2, -1, 6, 5, 4, -3, 3 };
var tree = new FenwickTree(nums.Length);
for (int i = 0; i < nums.Length; i++) tree.Add(i, nums[i]);
Console.WriteLine(tree.PrefixSum(4)); // 15
Console.WriteLine(tree.RangeSum(2, 5)); // 14
tree.Add(3, 4); // nums[3] goes from 6 to 10.
Console.WriteLine(tree.RangeSum(2, 5)); // 18
Console.WriteLine(tree.RangeSum(0, 7)); // 23
Console.WriteLine(tree.RangeSum(6, 6)); // -3
}
}public class Solution {
// Prefix sums over an array that changes. Positions are 1-indexed inside:
// tree[i] holds the sum of the (i & -i) values that end at position i.
static class FenwickTree {
private final int[] tree;
FenwickTree(int n) {
// Slot 0 stays unused: 0 & -0 is 0, so the loops would never move.
tree = new int[n + 1];
}
// Add delta to nums[i].
void add(int i, int delta) {
i++; // Shift to 1-indexed.
while (i < tree.length) {
tree[i] += delta;
i += i & -i; // Climb to the next block that also covers this position.
}
}
// Sum of nums[0..i], inclusive.
int prefixSum(int i) {
i++;
int total = 0;
while (i > 0) {
total += tree[i];
i -= i & -i; // Drop the lowest set bit: jump to the block just before this one.
}
return total;
}
// Sum of nums[left..right], inclusive.
int rangeSum(int left, int right) {
return prefixSum(right) - prefixSum(left - 1);
}
}
public static void main(String[] args) {
int[] nums = {3, 2, -1, 6, 5, 4, -3, 3};
FenwickTree tree = new FenwickTree(nums.length);
for (int i = 0; i < nums.length; i++) tree.add(i, nums[i]);
System.out.println(tree.prefixSum(4)); // 15
System.out.println(tree.rangeSum(2, 5)); // 14
tree.add(3, 4); // nums[3] goes from 6 to 10.
System.out.println(tree.rangeSum(2, 5)); // 18
System.out.println(tree.rangeSum(0, 7)); // 23
System.out.println(tree.rangeSum(6, 6)); // -3
}
}Worked Problems
Each solution stays folded until you open it, so you can try the problem first. Every one is a complete program in Python, TypeScript, Go, C# and Java, run and checked against its expected output.
Problem
Build a class over an integer array nums with two operations. update(index, val) sets nums[index] to val, and sumRange(left, right) returns the sum of nums[left] through nums[right], inclusive. The two kinds of call arrive interleaved, many of each.
Example: for nums = [1, 3, 5], sumRange(0, 2) returns 9. After update(1, 2) the array is [1, 2, 5], and sumRange(0, 2) returns 8.
Show SolutionHide Solution
Approach
This is a segment tree stored in a flat array, numbered like the array layout from Heaps but starting at 1: node k has children 2k and 2k + 1. build fills the leaves and adds each pair on the way back up, which takes O(n).
update walks from the root down to the one leaf that holds index, always picking the half that contains it. It sets the leaf, then recomputes each sum on the way back up. That's one node per level, so O(log n).
sumRange asks each node how its range overlaps the query:
- No overlap: return 0 without looking further.
- Fully inside: return the stored sum. This is where the speed comes from, because a whole block is answered in one step.
- Partial overlap: ask both children and add their answers.
Only nodes that straddle an end of the query get split, and there are at most two of those per level, so a query visits O(log n) nodes. The array has 4n slots because, when n isn't a power of two, node numbers can run past 2n. 4n is always enough.
Time O(n) to build, O(log n) per update or sumRangeSpace O(n)
class NumArray:
"""Segment tree for range sums with point updates. Node 1 covers the whole
array, and node k's children 2k and 2k + 1 each cover half of its range."""
def __init__(self, nums: list[int]) -> None:
self.n = len(nums)
self.tree = [0] * (4 * self.n) # 4n slots always fit every node.
self._build(nums, 1, 0, self.n - 1)
def update(self, index: int, val: int) -> None:
"""Set nums[index] to val."""
self._update_node(1, 0, self.n - 1, index, val)
def sum_range(self, left: int, right: int) -> int:
"""Sum of nums[left..right], inclusive."""
return self._query_node(1, 0, self.n - 1, left, right)
def _build(self, nums: list[int], node: int, lo: int, hi: int) -> None:
if lo == hi:
self.tree[node] = nums[lo]
return
mid = (lo + hi) // 2
self._build(nums, 2 * node, lo, mid)
self._build(nums, 2 * node + 1, mid + 1, hi)
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
def _update_node(self, node: int, lo: int, hi: int, index: int, val: int) -> None:
if lo == hi:
self.tree[node] = val
return
# Only one half holds index. Fix that half, then recompute this node's sum.
mid = (lo + hi) // 2
if index <= mid:
self._update_node(2 * node, lo, mid, index, val)
else:
self._update_node(2 * node + 1, mid + 1, hi, index, val)
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
def _query_node(self, node: int, lo: int, hi: int, left: int, right: int) -> int:
if right < lo or hi < left:
return 0 # No overlap: this node adds nothing.
if left <= lo and hi <= right:
return self.tree[node] # Fully inside: use the stored sum.
# Partial overlap: split the question between the two halves.
mid = (lo + hi) // 2
return (
self._query_node(2 * node, lo, mid, left, right)
+ self._query_node(2 * node + 1, mid + 1, hi, left, right)
)
if __name__ == "__main__":
arr = NumArray([1, 3, 5])
print(arr.sum_range(0, 2)) # 9
arr.update(1, 2)
print(arr.sum_range(0, 2)) # 8
arr = NumArray([5, 8, 6, 3, 2, 7, 2, 6])
print(arr.sum_range(2, 5)) # 18
arr.update(3, 10)
print(arr.sum_range(2, 5)) # 25
print(arr.sum_range(7, 7)) # 6// Segment tree for range sums with point updates. Node 1 covers the whole
// array, and node k's children 2k and 2k + 1 each cover half of its range.
export class NumArray {
private n: number;
private tree: number[];
constructor(nums: number[]) {
this.n = nums.length;
this.tree = new Array<number>(4 * this.n).fill(0); // 4n slots always fit every node.
this.build(nums, 1, 0, this.n - 1);
}
// Set nums[index] to val.
update(index: number, val: number): void {
this.updateNode(1, 0, this.n - 1, index, val);
}
// Sum of nums[left..right], inclusive.
sumRange(left: number, right: number): number {
return this.queryNode(1, 0, this.n - 1, left, right);
}
private build(nums: number[], node: number, lo: number, hi: number): void {
if (lo === hi) {
this.tree[node] = nums[lo];
return;
}
const mid = Math.floor((lo + hi) / 2);
this.build(nums, 2 * node, lo, mid);
this.build(nums, 2 * node + 1, mid + 1, hi);
this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
}
private updateNode(node: number, lo: number, hi: number, index: number, val: number): void {
if (lo === hi) {
this.tree[node] = val;
return;
}
// Only one half holds index. Fix that half, then recompute this node's sum.
const mid = Math.floor((lo + hi) / 2);
if (index <= mid) this.updateNode(2 * node, lo, mid, index, val);
else this.updateNode(2 * node + 1, mid + 1, hi, index, val);
this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
}
private queryNode(node: number, lo: number, hi: number, left: number, right: number): number {
if (right < lo || hi < left) return 0; // No overlap: this node adds nothing.
if (left <= lo && hi <= right) return this.tree[node]; // Fully inside: use the stored sum.
// Partial overlap: split the question between the two halves.
const mid = Math.floor((lo + hi) / 2);
return (
this.queryNode(2 * node, lo, mid, left, right) +
this.queryNode(2 * node + 1, mid + 1, hi, left, right)
);
}
}
let arr = new NumArray([1, 3, 5]);
console.log(arr.sumRange(0, 2)); // 9
arr.update(1, 2);
console.log(arr.sumRange(0, 2)); // 8
arr = new NumArray([5, 8, 6, 3, 2, 7, 2, 6]);
console.log(arr.sumRange(2, 5)); // 18
arr.update(3, 10);
console.log(arr.sumRange(2, 5)); // 25
console.log(arr.sumRange(7, 7)); // 6package main
import "fmt"
// numArray is a segment tree for range sums with point updates. Node 1
// covers the whole array, and node k's children 2k and 2k + 1 each cover
// half of its range.
type numArray struct {
n int
tree []int
}
func newNumArray(nums []int) *numArray {
a := &numArray{n: len(nums), tree: make([]int, 4*len(nums))} // 4n slots always fit every node.
a.build(nums, 1, 0, a.n-1)
return a
}
// update sets nums[index] to val.
func (a *numArray) update(index, val int) {
a.updateNode(1, 0, a.n-1, index, val)
}
// sumRange returns the sum of nums[left..right], inclusive.
func (a *numArray) sumRange(left, right int) int {
return a.queryNode(1, 0, a.n-1, left, right)
}
func (a *numArray) build(nums []int, node, lo, hi int) {
if lo == hi {
a.tree[node] = nums[lo]
return
}
mid := (lo + hi) / 2
a.build(nums, 2*node, lo, mid)
a.build(nums, 2*node+1, mid+1, hi)
a.tree[node] = a.tree[2*node] + a.tree[2*node+1]
}
func (a *numArray) updateNode(node, lo, hi, index, val int) {
if lo == hi {
a.tree[node] = val
return
}
// Only one half holds index. Fix that half, then recompute this node's sum.
mid := (lo + hi) / 2
if index <= mid {
a.updateNode(2*node, lo, mid, index, val)
} else {
a.updateNode(2*node+1, mid+1, hi, index, val)
}
a.tree[node] = a.tree[2*node] + a.tree[2*node+1]
}
func (a *numArray) queryNode(node, lo, hi, left, right int) int {
if right < lo || hi < left {
return 0 // No overlap: this node adds nothing.
}
if left <= lo && hi <= right {
return a.tree[node] // Fully inside: use the stored sum.
}
// Partial overlap: split the question between the two halves.
mid := (lo + hi) / 2
return a.queryNode(2*node, lo, mid, left, right) +
a.queryNode(2*node+1, mid+1, hi, left, right)
}
func main() {
arr := newNumArray([]int{1, 3, 5})
fmt.Println(arr.sumRange(0, 2)) // 9
arr.update(1, 2)
fmt.Println(arr.sumRange(0, 2)) // 8
arr = newNumArray([]int{5, 8, 6, 3, 2, 7, 2, 6})
fmt.Println(arr.sumRange(2, 5)) // 18
arr.update(3, 10)
fmt.Println(arr.sumRange(2, 5)) // 25
fmt.Println(arr.sumRange(7, 7)) // 6
}using System;
public class Solution
{
// Segment tree for range sums with point updates. Node 1 covers the whole
// array, and node k's children 2k and 2k + 1 each cover half of its range.
public class NumArray
{
readonly int n;
readonly int[] tree;
public NumArray(int[] nums)
{
n = nums.Length;
tree = new int[4 * n]; // 4n slots always fit every node.
Build(nums, 1, 0, n - 1);
}
// Set nums[index] to val.
public void Update(int index, int val) => UpdateNode(1, 0, n - 1, index, val);
// Sum of nums[left..right], inclusive.
public int SumRange(int left, int right) => QueryNode(1, 0, n - 1, left, right);
void Build(int[] nums, int node, int lo, int hi)
{
if (lo == hi)
{
tree[node] = nums[lo];
return;
}
int mid = (lo + hi) / 2;
Build(nums, 2 * node, lo, mid);
Build(nums, 2 * node + 1, mid + 1, hi);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
void UpdateNode(int node, int lo, int hi, int index, int val)
{
if (lo == hi)
{
tree[node] = val;
return;
}
// Only one half holds index. Fix that half, then recompute this node's sum.
int mid = (lo + hi) / 2;
if (index <= mid) UpdateNode(2 * node, lo, mid, index, val);
else UpdateNode(2 * node + 1, mid + 1, hi, index, val);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
int QueryNode(int node, int lo, int hi, int left, int right)
{
if (right < lo || hi < left) return 0; // No overlap: this node adds nothing.
if (left <= lo && hi <= right) return tree[node]; // Fully inside: use the stored sum.
// Partial overlap: split the question between the two halves.
int mid = (lo + hi) / 2;
return QueryNode(2 * node, lo, mid, left, right)
+ QueryNode(2 * node + 1, mid + 1, hi, left, right);
}
}
public static void Main()
{
var arr = new NumArray(new[] { 1, 3, 5 });
Console.WriteLine(arr.SumRange(0, 2)); // 9
arr.Update(1, 2);
Console.WriteLine(arr.SumRange(0, 2)); // 8
arr = new NumArray(new[] { 5, 8, 6, 3, 2, 7, 2, 6 });
Console.WriteLine(arr.SumRange(2, 5)); // 18
arr.Update(3, 10);
Console.WriteLine(arr.SumRange(2, 5)); // 25
Console.WriteLine(arr.SumRange(7, 7)); // 6
}
}public class Solution {
// Segment tree for range sums with point updates. Node 1 covers the whole
// array, and node k's children 2k and 2k + 1 each cover half of its range.
static class NumArray {
private final int n;
private final int[] tree;
NumArray(int[] nums) {
n = nums.length;
tree = new int[4 * n]; // 4n slots always fit every node.
build(nums, 1, 0, n - 1);
}
// Set nums[index] to val.
void update(int index, int val) {
updateNode(1, 0, n - 1, index, val);
}
// Sum of nums[left..right], inclusive.
int sumRange(int left, int right) {
return queryNode(1, 0, n - 1, left, right);
}
private void build(int[] nums, int node, int lo, int hi) {
if (lo == hi) {
tree[node] = nums[lo];
return;
}
int mid = (lo + hi) / 2;
build(nums, 2 * node, lo, mid);
build(nums, 2 * node + 1, mid + 1, hi);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
private void updateNode(int node, int lo, int hi, int index, int val) {
if (lo == hi) {
tree[node] = val;
return;
}
// Only one half holds index. Fix that half, then recompute this node's sum.
int mid = (lo + hi) / 2;
if (index <= mid) updateNode(2 * node, lo, mid, index, val);
else updateNode(2 * node + 1, mid + 1, hi, index, val);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
private int queryNode(int node, int lo, int hi, int left, int right) {
if (right < lo || hi < left) return 0; // No overlap: this node adds nothing.
if (left <= lo && hi <= right) return tree[node]; // Fully inside: use the stored sum.
// Partial overlap: split the question between the two halves.
int mid = (lo + hi) / 2;
return queryNode(2 * node, lo, mid, left, right)
+ queryNode(2 * node + 1, mid + 1, hi, left, right);
}
}
public static void main(String[] args) {
NumArray arr = new NumArray(new int[] {1, 3, 5});
System.out.println(arr.sumRange(0, 2)); // 9
arr.update(1, 2);
System.out.println(arr.sumRange(0, 2)); // 8
arr = new NumArray(new int[] {5, 8, 6, 3, 2, 7, 2, 6});
System.out.println(arr.sumRange(2, 5)); // 18
arr.update(3, 10);
System.out.println(arr.sumRange(2, 5)); // 25
System.out.println(arr.sumRange(7, 7)); // 6
}
}Problem
Given an integer array nums, return an array counts where counts[i] is the number of elements to the right of index i that are strictly smaller than nums[i].
Example: [5, 2, 6, 1] returns [2, 1, 1, 0]. Two values right of 5 are smaller (2 and 1), one right of 2 (1), one right of 6 (1), and nothing sits right of the final 1.
Show SolutionHide Solution
Approach
Checking every pair is O(n²). Instead, walk from right to left and keep a tally of the values you've passed. When you reach nums[i], the tally holds exactly the values to its right, and the answer is how many of them are smaller: a prefix sum over the tally. Then add nums[i] to the tally and move on. A Fenwick tree indexed by value does both steps in O(log n).
The catch is that values can be negative (and in similar problems as large as 10^9), so they can't index an array directly. Coordinate compression fixes that: sort the distinct values and replace each value with its rank. Ranks run from 0 to at most n - 1 and keep the order of the values, which is all the query cares about.
ranks: 1 -> 0, 2 -> 1, 5 -> 2, 6 -> 3 i nums[i] rank prefixSum(rank - 1) seen afterward 3 1 0 0 [1, 0, 0, 0] 2 6 3 1 [1, 0, 0, 1] 1 2 1 1 [1, 1, 0, 1] 0 5 2 2 [1, 1, 1, 1]
Counting Smaller Values With a Fenwick Tree
Step 1 of 15
nums
seen.tree
- Value being placed, block being added to
- Block being read
- Already in the tree, or counted
Ranks stand in for the values: 1, 2, 5, 6 become 0, 1, 2, 3, at tree positions 1..4. Walk from the right, so seen only holds the values after i.
All 15 steps as text
- Ranks stand in for the values:
1, 2, 5, 6become0, 1, 2, 3, at tree positions1..4. Walk from the right, soseenonly holds the values afteri. nums[3] = 1has rank0. No rank is below0, soprefixSum(-1)reads nothing andcounts[3] = 0.- Add rank
0toseen, at position1.tree[1]covers position1alone, so it goes up to1. 1 + (1 & -1) = 2is the next block that also covers position1.tree[2]covers positions1..2, so it goes up to1.2 + (2 & -2) = 4is the next block that also covers position1.tree[4]covers positions1..4, so it goes up to1. The next jump, to8, is past the end.nums[2] = 6has rank3.prefixSum(2)counts the smaller ranks from position3down.tree[3]covers position3alone and holds0.3 - (3 & -3) = 2, the block just before.tree[2]covers positions1..2and holds1, so the total is0 + 1 = 1. Clearing its lowest bit leaves0, socounts[2] = 1.- Add rank
3toseen, at position4.tree[4]covers positions1..4, so it goes up to2. The next jump, to8, is past the end. nums[1] = 2has rank1.prefixSum(0)counts the smaller ranks from position1down.tree[1]covers position1alone and holds1. Clearing its lowest bit leaves0, socounts[1] = 1.- Add rank
1toseen, at position2.tree[2]covers positions1..2, so it goes up to2. 2 + (2 & -2) = 4is the next block that also covers position2.tree[4]covers positions1..4, so it goes up to3. The next jump, to8, is past the end.nums[0] = 5has rank2.prefixSum(1)counts the smaller ranks from position2down.tree[2]covers positions1..2and holds2. Clearing its lowest bit leaves0, socounts[0] = 2.- Add rank
2toseen, at position3.tree[3]covers position3alone, so it goes up to1. 3 + (3 & -3) = 4is the next block that also covers position3.tree[4]covers positions1..4, so it goes up to4. The next jump, to8, is past the end.counts = [2, 1, 1, 0]. Each value cost one prefix sum and one add, each touching at most about log n blocks, instead of rescanning everything to its right.
The query stops at rank - 1 because the problem wants strictly smaller values. Equal values share a rank, so they're left out.
Time O(n log n)Space O(n)
def count_smaller(nums: list[int]) -> list[int]:
"""For each nums[i], how many values to its right are strictly smaller."""
# Coordinate compression: replace each value with its rank among the
# distinct values, so the tree needs one slot per distinct value.
distinct = sorted(set(nums))
rank = {value: r for r, value in enumerate(distinct)}
seen = FenwickTree(len(distinct)) # How many of each rank we've passed.
counts = [0] * len(nums)
# Walk right to left, so the tree holds exactly the values after i.
for i in range(len(nums) - 1, -1, -1):
r = rank[nums[i]]
counts[i] = seen.prefix_sum(r - 1) # Ranks below r are the strictly smaller values.
seen.add(r, 1)
return counts
class FenwickTree:
"""The Fenwick tree from the template: tree[i] (1-indexed) holds the sum
of the (i & -i) values that end at position i."""
def __init__(self, n: int) -> None:
self.tree = [0] * (n + 1)
def add(self, i: int, delta: int) -> None:
i += 1
while i < len(self.tree):
self.tree[i] += delta
i += i & -i
def prefix_sum(self, i: int) -> int:
"""Sum of positions 0..i, inclusive. prefix_sum(-1) is 0."""
i += 1
total = 0
while i > 0:
total += self.tree[i]
i -= i & -i
return total
if __name__ == "__main__":
print(count_smaller([5, 2, 6, 1])) # [2, 1, 1, 0]
print(count_smaller([-1, -1])) # [0, 0]
print(count_smaller([100, -50, 7, 100, -50])) # [3, 0, 1, 1, 0]// For each nums[i], how many values to its right are strictly smaller.
export function countSmaller(nums: number[]): number[] {
// Coordinate compression: replace each value with its rank among the
// distinct values, so the tree needs one slot per distinct value.
const sorted = [...new Set(nums)].sort((a, b) => a - b);
const rank = new Map<number, number>();
sorted.forEach((value, r) => rank.set(value, r));
const seen = new FenwickTree(sorted.length); // How many of each rank we've passed.
const counts = new Array<number>(nums.length).fill(0);
// Walk right to left, so the tree holds exactly the values after i.
for (let i = nums.length - 1; i >= 0; i--) {
const r = rank.get(nums[i])!;
counts[i] = seen.prefixSum(r - 1); // Ranks below r are the strictly smaller values.
seen.add(r, 1);
}
return counts;
}
// The Fenwick tree from the template: tree[i] (1-indexed) holds the sum of
// the (i & -i) values that end at position i.
class FenwickTree {
private tree: number[];
constructor(n: number) {
this.tree = new Array<number>(n + 1).fill(0);
}
add(i: number, delta: number): void {
for (i++; i < this.tree.length; i += i & -i) this.tree[i] += delta;
}
// Sum of positions 0..i, inclusive. prefixSum(-1) is 0.
prefixSum(i: number): number {
let total = 0;
for (i++; i > 0; i -= i & -i) total += this.tree[i];
return total;
}
}
console.log(JSON.stringify(countSmaller([5, 2, 6, 1]))); // [2,1,1,0]
console.log(JSON.stringify(countSmaller([-1, -1]))); // [0,0]
console.log(JSON.stringify(countSmaller([100, -50, 7, 100, -50]))); // [3,0,1,1,0]package main
import (
"fmt"
"slices"
)
// countSmaller returns, for each nums[i], how many values to its right are
// strictly smaller.
func countSmaller(nums []int) []int {
// Coordinate compression: replace each value with its rank among the
// distinct values, so the tree needs one slot per distinct value.
distinct := slices.Clone(nums)
slices.Sort(distinct)
distinct = slices.Compact(distinct)
rank := make(map[int]int, len(distinct))
for r, value := range distinct {
rank[value] = r
}
seen := newFenwickTree(len(distinct)) // How many of each rank we've passed.
counts := make([]int, len(nums))
// Walk right to left, so the tree holds exactly the values after i.
for i := len(nums) - 1; i >= 0; i-- {
r := rank[nums[i]]
counts[i] = seen.prefixSum(r - 1) // Ranks below r are the strictly smaller values.
seen.add(r, 1)
}
return counts
}
// fenwickTree is the Fenwick tree from the template: tree[i] (1-indexed)
// holds the sum of the (i & -i) values that end at position i.
type fenwickTree struct {
tree []int
}
func newFenwickTree(n int) *fenwickTree {
return &fenwickTree{tree: make([]int, n+1)}
}
func (f *fenwickTree) add(i, delta int) {
for i++; i < len(f.tree); i += i & -i {
f.tree[i] += delta
}
}
// prefixSum returns the sum of positions 0..i, inclusive. prefixSum(-1) is 0.
func (f *fenwickTree) prefixSum(i int) int {
total := 0
for i++; i > 0; i -= i & -i {
total += f.tree[i]
}
return total
}
func main() {
fmt.Println(countSmaller([]int{5, 2, 6, 1})) // [2 1 1 0]
fmt.Println(countSmaller([]int{-1, -1})) // [0 0]
fmt.Println(countSmaller([]int{100, -50, 7, 100, -50})) // [3 0 1 1 0]
}using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
// For each nums[i], how many values to its right are strictly smaller.
public static int[] CountSmaller(int[] nums)
{
// Coordinate compression: replace each value with its rank among the
// distinct values, so the tree needs one slot per distinct value.
int[] distinct = nums.Distinct().OrderBy(v => v).ToArray();
var rank = new Dictionary<int, int>();
for (int r = 0; r < distinct.Length; r++) rank[distinct[r]] = r;
var seen = new FenwickTree(distinct.Length); // How many of each rank we've passed.
var counts = new int[nums.Length];
// Walk right to left, so the tree holds exactly the values after i.
for (int i = nums.Length - 1; i >= 0; i--)
{
int r = rank[nums[i]];
counts[i] = seen.PrefixSum(r - 1); // Ranks below r are the strictly smaller values.
seen.Add(r, 1);
}
return counts;
}
// The Fenwick tree from the template: tree[i] (1-indexed) holds the sum of
// the (i & -i) values that end at position i.
public class FenwickTree
{
readonly int[] tree;
public FenwickTree(int n)
{
tree = new int[n + 1];
}
public void Add(int i, int delta)
{
for (i++; i < tree.Length; i += i & -i) tree[i] += delta;
}
// Sum of positions 0..i, inclusive. PrefixSum(-1) is 0.
public int PrefixSum(int i)
{
int total = 0;
for (i++; i > 0; i -= i & -i) total += tree[i];
return total;
}
}
public static void Main()
{
Console.WriteLine(Format(CountSmaller(new[] { 5, 2, 6, 1 }))); // [2, 1, 1, 0]
Console.WriteLine(Format(CountSmaller(new[] { -1, -1 }))); // [0, 0]
Console.WriteLine(Format(CountSmaller(new[] { 100, -50, 7, 100, -50 }))); // [3, 0, 1, 1, 0]
}
static string Format(int[] values) => "[" + string.Join(", ", values) + "]";
}import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class Solution {
// For each nums[i], how many values to its right are strictly smaller.
static int[] countSmaller(int[] nums) {
// Coordinate compression: replace each value with its rank among the
// distinct values, so the tree needs one slot per distinct value.
int[] distinct = Arrays.stream(nums).distinct().sorted().toArray();
Map<Integer, Integer> rank = new HashMap<>();
for (int r = 0; r < distinct.length; r++) rank.put(distinct[r], r);
FenwickTree seen = new FenwickTree(distinct.length); // How many of each rank we've passed.
int[] counts = new int[nums.length];
// Walk right to left, so the tree holds exactly the values after i.
for (int i = nums.length - 1; i >= 0; i--) {
int r = rank.get(nums[i]);
counts[i] = seen.prefixSum(r - 1); // Ranks below r are the strictly smaller values.
seen.add(r, 1);
}
return counts;
}
// The Fenwick tree from the template: tree[i] (1-indexed) holds the sum of
// the (i & -i) values that end at position i.
static class FenwickTree {
private final int[] tree;
FenwickTree(int n) {
tree = new int[n + 1];
}
void add(int i, int delta) {
for (i++; i < tree.length; i += i & -i) tree[i] += delta;
}
// Sum of positions 0..i, inclusive. prefixSum(-1) is 0.
int prefixSum(int i) {
int total = 0;
for (i++; i > 0; i -= i & -i) total += tree[i];
return total;
}
}
public static void main(String[] args) {
System.out.println(Arrays.toString(countSmaller(new int[] {5, 2, 6, 1}))); // [2, 1, 1, 0]
System.out.println(Arrays.toString(countSmaller(new int[] {-1, -1}))); // [0, 0]
System.out.println(Arrays.toString(countSmaller(new int[] {100, -50, 7, 100, -50}))); // [3, 0, 1, 1, 0]
}
}Common Pitfalls
- Using index 0 in a Fenwick tree.
0 & -0is 0, so the update loop never advances. Shift indices to start at 1. - Treating LeetCode 307's
updateas an add. It sets the value, so with a Fenwick tree you addval - nums[index]and keep your copy of the array current. - Sizing a recursive segment tree at
2n. When n isn't a power of two, node numbers can run past2n;4nis always enough. - Counting
<=instead of<when values repeat. For strictly smaller values, query up torank - 1, notrank. - Using a Fenwick tree for range minimum or maximum. Those can't be undone by subtraction, so a range can't be split into two prefixes. Use a segment tree.
Practice
More problems to try on your own.