Segment trees and Fenwick trees
Answer range queries (sum, minimum, maximum) and apply updates in O(log n) each: how a segment tree splits ranges, the compact bottom-up version, and the tiny Fenwick tree built on one bit trick.
| Structure | Range query | Point update | Notes |
|---|---|---|---|
The segment tree
int[] tonnes = { 5, 8, 6, 3, 9, 2, 7, 4 };var tree = new SegmentTree(tonnes);Console.WriteLine($"Days 2-6: {tree.Query(2, 6)}");Console.WriteLine($"All days: {tree.Query(0, 7)}");tree.Update(4, 1); // day 4 corrected from 9 to 1Console.WriteLine($"Days 2-6: {tree.Query(2, 6)}"); class SegmentTree{ private readonly int[] sum; private readonly int n; public SegmentTree(int[] values) { n = values.Length; sum = new int[4 * n]; // always enough room Build(1, 0, n - 1, values); } private void Build(int node, int lo, int hi, int[] v) { if (lo == hi) { sum[node] = v[lo]; return; } int mid = (lo + hi) / 2; Build(2 * node, lo, mid, v); // children of node k are 2k and 2k + 1 Build(2 * node + 1, mid + 1, hi, v); sum[node] = sum[2 * node] + sum[2 * node + 1]; } public int Query(int l, int r) => Query(1, 0, n - 1, l, r); private int Query(int node, int lo, int hi, int l, int r) { if (r < lo || hi < l) return 0; // outside: skip if (l <= lo && hi <= r) return sum[node]; // inside: use the stored sum int mid = (lo + hi) / 2; // partly inside: ask both children return Query(2 * node, lo, mid, l, r) + Query(2 * node + 1, mid + 1, hi, l, r); } public void Update(int i, int value) => Update(1, 0, n - 1, i, value); private void Update(int node, int lo, int hi, int i, int value) { if (lo == hi) { sum[node] = value; return; } int mid = (lo + hi) / 2; if (i <= mid) Update(2 * node, lo, mid, i, value); else Update(2 * node + 1, mid + 1, hi, i, value); sum[node] = sum[2 * node] + sum[2 * node + 1]; // fix the sums on the way back up }}Days 2-6: 27 All days: 44 Days 2-6: 19
Any associative operation
+ with Math.Min and 0 with int.MaxValue, and you get range minimum queries. Max, gcd, “count of defects”, even “matrix product” work the same way, as long as the operation is associative: (a ∘ b) ∘ c = a ∘ (b ∘ c).
int[] temps = { 14, 9, 17, 6, 11, 8, 20, 12 }; // midday temperatures, days 0-7int n = temps.Length;var t = new int[2 * n];for (int i = 0; i < n; i++) t[n + i] = temps[i]; // leaves at n .. 2n - 1for (int i = n - 1; i >= 1; i--) t[i] = Math.Min(t[2 * i], t[2 * i + 1]); Console.WriteLine(Min(0, 2));Console.WriteLine(Min(3, 6));Console.WriteLine(Min(4, 7)); int Min(int l, int r) // inclusive range l..r{ int best = int.MaxValue; for (l += n, r += n + 1; l < r; l /= 2, r /= 2) { if (l % 2 == 1) best = Math.Min(best, t[l++]); // l is a right child: take it, move right if (r % 2 == 1) best = Math.Min(best, t[--r]); // r is a right child: take its left sibling } return best;}9 6 8
The Fenwick tree
t[i] (counting from 1) stores the sum of the lowbit(i) values that end at position i, where lowbit(i) = i & -i is the lowest set bit of i: t[6] covers 2 values (6 = 110₂), t[8] covers 8 (8 = 1000₂), t[7] covers 1.
Prefix sum up to i: add t[i], then jump to i -= i & -i(remove the lowest bit), until i is 0. For i = 7: t[7] + t[6] + t[4].Update at i: add the change to t[i], then jump to i += i & -i, until past the end. These are exactly the cells whose range contains i.Range sum l..r: prefix(r) − prefix(l − 1).
int[] tonnes = { 5, 8, 6, 3, 9, 2, 7, 4 };var fw = new Fenwick(tonnes.Length);for (int i = 0; i < tonnes.Length; i++) fw.Add(i, tonnes[i]); Console.WriteLine($"Days 0-6: {fw.PrefixSum(6)}");Console.WriteLine($"Days 2-6: {fw.RangeSum(2, 6)}");fw.Add(4, -8); // day 4: 9 -> 1Console.WriteLine($"Days 2-6: {fw.RangeSum(2, 6)}"); class Fenwick{ private readonly int[] t; // 1-based: t[i] covers the (i & -i) values ending at i public Fenwick(int n) => t = new int[n + 1]; public void Add(int index, int delta) { for (int i = index + 1; i < t.Length; i += i & -i) t[i] += delta; } public int PrefixSum(int index) // sum of values 0..index { int s = 0; for (int i = index + 1; i > 0; i -= i & -i) s += t[i]; return s; } public int RangeSum(int l, int r) => PrefixSum(r) - (l > 0 ? PrefixSum(l - 1) : 0);}Days 0-6: 40 Days 2-6: 27 Days 2-6: 19
| Segment tree | Fenwick tree | |
|---|---|---|
A classic trick: counting with a Fenwick tree
PrefixSum(v) answers “how many values seen so far are ≤ v?” in O(log n). This counts inversions, ranks scores on a live leaderboard and answers “how many earlier deliveries were lighter than this one?”.
{ 3, 1, 4, 1, 5, 2 }, print for each load how many earlier loads were strictly lighter: 0 0 2 0 4 2. Use a Fenwick tree indexed by weight so each answer takes O(log n).
Show a hint
Show the solution
int[] loads = { 3, 1, 4, 1, 5, 2 };int max = loads.Max();var t = new int[max + 1]; // Fenwick tree over weights 1..maxvar result = new List<int>();foreach (int w in loads){ result.Add(CountUpTo(w - 1)); // earlier loads strictly lighter for (int i = w; i <= max; i += i & -i) t[i]++; // record this weight}Console.WriteLine(string.Join(" ", result)); int CountUpTo(int i){ int s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s;}0 0 2 0 4 2
Remember
Prefix sums are fast to query but slow to update; segment and Fenwick trees make both O(log n). A segment tree stores the combined value of each range; a query uses fully covered nodes and skips the rest. Any associative operation works in a segment tree; lazy propagation adds O(log n) range updates. A Fenwick tree is one array and two loops built on i & -i; it handles prefix sums, range sums and counting.