On this page

Capstone: A Range-Query Engine

Module 3 gave you three ways to answer questions about a contiguous slice of an array while the array keeps changing: the segment tree with lazy propagation, the Fenwick tree, and sqrt decomposition. Each was presented on its own, with its own interface and its own favourite problem. This capstone puts them behind one API, makes them agree with a brute-force oracle on hundreds of thousands of random operations, and then measures them against each other so you learn what the versus difference is worth in real time — and where it is not worth what the asymptotics suggest.

Time-series rollups, leaderboards and order-book depth queries all sit on one of these three structures, and the engineering questions are always the same: which operations does the workload need, which structure supports them, and is the faster one worth its complexity?

Goal

When you finish you will have:

  1. A RangeEngine interface with five operations — point_set, range_add, range_sum, range_min, range_max — and a capability flag for structures that cannot support all of them.
  2. Four implementations: a brute-force oracle, a lazy segment tree, a Fenwick tree (sum only, with range updates via two trees), and sqrt decomposition with per-block lazy adds.
  3. A deterministic acceptance test and a randomized stress test that drives all four with the same operation stream and asserts identical answers after every query.
  4. A benchmark table: build time and time per operation for each structure at , and , on a sum workload and a min/max workload, with a short write-up explaining the numbers.

Requirements

  • Array: signed 64-bit integers, indices . All ranges are inclusive [l, r] with .
  • point_set(i, v): set element to .
  • range_add(l, r, d): add to every element in [l, r].
  • range_sum(l, r), range_min(l, r), range_max(l, r): the aggregate over [l, r] of the current values.
  • Capability flag supports_min_max: an engine that cannot answer min/max (the Fenwick tree) must say so and must raise an error rather than return a wrong answer.
  • Complexity targets: segment tree per operation, build; Fenwick per operation; sqrt decomposition per operation, build; oracle per operation.
  • No overflow: with , , and at most operations, values stay below about and sums below about — inside 64 bits, provided every intermediate is 64-bit, including d * length in the lazy apply and d * l in the Fenwick update. TypeScript's number is exact only up to , so there use smaller limits or BigInt.

Why the Fenwick tree gets a capability flag

A Fenwick tree stores prefix aggregates and answers a range as prefix(r + 1) - prefix(l). That subtraction needs an inverse: sum has one, min and max do not. You cannot recover min(a[l..r]) from min(a[0..r]) and min(a[0..l-1]), and the Fenwick prefix-min variants do not survive arbitrary range_add. So the engine declares what it can do, like a database index type that supports = and < but not LIKE '%x'.

Staged plan

flowchart LR
    P1["Part 1<br/>interface + oracle<br/>+ acceptance test"] --> P2["Part 2<br/>lazy segment tree"]
    P2 --> P3["Part 3<br/>Fenwick with<br/>range add"]
    P3 --> P4["Part 4<br/>sqrt decomposition"]
    P4 --> P5["Part 5<br/>stress test<br/>all four together"]
    P5 --> P6["Part 6<br/>benchmark<br/>+ write-up"]

Part 1 — the interface and the oracle

Define the interface first (a Python protocol or base class, a Java interface, a C++ abstract class, a TypeScript interface). Then write the oracle: a plain array whose range_add loops over [l, r] and whose queries loop and aggregate. Every operation is , and that is the point. The oracle has to be so simple that you can verify it by reading it, because every other implementation will be judged against it.

Write the acceptance sequence below as a test and make the oracle pass it before writing anything else.

Part 2 — lazy segment tree

Each node covers a range and stores three aggregates — sum, min, max — plus a pending lazy add. The key fact that makes one tree serve all three queries: adding to every element of a node's range changes the aggregates in without touching the children:

So apply(node, d) updates the three aggregates and accumulates lazy += d; push(node) hands a node's lazy to its two children before you descend through it; pull(node) recomputes the aggregates from the children after you return. A range add or query touches nodes: at most two partially covered nodes per level, as proved in Segment Trees in Depth.

Implement point_set(i, v) either as a dedicated descent that sets a leaf, or — simpler and still — as range_add(i, i, v - range_sum(i, i)).

flowchart TD
    Q["range_add or query on node covering l..r"] --> D{"query range covers node fully?"}
    D -->|"disjoint"| X["return, nothing to do"]
    D -->|"fully covered"| A["apply d or read aggregates, O(1)"]
    D -->|"partial"| P["push lazy to both children"]
    P --> L["recurse left and right"]
    L --> U["pull: recompute sum, min, max"]

Part 3 — Fenwick tree with range add and range sum

A single Fenwick tree does point add + prefix sum. For range add + range sum keep two trees, and . Adding to [l, r] (0-based, with prefix length meaning elements ) is four point updates:

and the prefix sum of the first elements is . To see why, consider one update and a prefix length with : the true contribution is , and the formula gives . For it gives , the full block. The Fenwick Trees lesson derives it in detail.

Build by calling range_add(i, i, a[i]) for every (), or in by the "add each node into its parent" construction (stretch goal 1). range_min and range_max raise.

Part 4 — sqrt decomposition

Cut the array into blocks of size (at least 1). Per block keep sum, min, max of the stored values and a block-level lazy add. The true value of element in block is a[i] + lazy[b].

  • range_add(l, r, d): elements in the partial blocks at either end are updated one by one and their block's stats rebuilt (); every block fully inside the range just gets lazy[b] += d ( blocks).
  • Queries: partial blocks element by element using a[i] + lazy[b]; full blocks via sum[b] + lazy[b] * B, min[b] + lazy[b], max[b] + lazy[b].
  • point_set(i, v): store a[i] = v - lazy[b] so that the true value is , then rebuild block .

With both parts cost . The block size is a tuning knob, and Part 6 asks you to turn it.

Part 5 — stress test all four together

This is the technique from Testing & Debugging Algorithms: differential testing against an oracle on random inputs. Build all four engines from the same random array, then generate a long stream of random operations and apply each to every engine. After every query, assert that each engine that supports it returns the oracle's answer, and include the engine name, , and in the failure message so the failing case is reproducible.

Choices that make the stress test find bugs fast:

  • Small , many runs. . Bugs in segment trees and block code live at boundaries — a range that ends exactly at a block edge, a single-element array, a query equal to the whole array — and small arrays hit boundaries constantly. is deliberately not a perfect square and not a power of two.
  • Uniform ranges are not enough on their own. Choosing uniformly and then uniformly in gives plenty of short and single-element ranges, which is what you want.
  • Mix updates and queries roughly evenly, so lazy values pile up several levels deep before being pushed.
  • A fixed seed, printed on failure, so a failing run can be replayed.
  • Mutation-test the test. Deliberately break one line (use r instead of r + 1 in the Fenwick update; forget the push in the segment tree query) and confirm the stress test fails within a second. A stress test that has never failed has not been shown to work.

Part 6 — benchmark and write-up

Measure, for (skip the oracle above ):

  • Build time from the initial array.
  • Sum workload: operations drawn uniformly from point_set, range_add, range_sum with uniformly random ranges.
  • Min/max workload: the same with range_min/range_max instead of range_sum (segment tree and sqrt decomposition only).
  • Block-size sweep for sqrt decomposition: .

Generate all operations before starting the clock, store them in an array, and time only the loop that applies them. Warm up JIT languages (Java, TypeScript) by running the workload once untimed. Repeat each measurement at least five times and report the median. The Benchmarks page covers the rest of the methodology.

Write one page: the table, and answers to (1) why the Fenwick tree wins the sum workload even though it does four tree walks per range add, (2) how big the segment-tree-versus-sqrt gap is at each and whether it matches versus , and (3) what the block-size sweep shows.

Acceptance tests

Start from [5, -2, 7, 0, 3, -4, 8, 1]. Every engine must produce these results (the Fenwick tree skips the min/max rows and must raise if asked):

#OperationArray afterExpected result
1range_sum(0, 7)unchanged18
2range_min(2, 5)unchanged−4
3range_max(0, 3)unchanged7
4range_add(1, 4, 3)[5, 1, 10, 3, 6, -4, 8, 1]—
5range_sum(0, 3)19
6range_max(1, 5)10
7point_set(5, 9)[5, 1, 10, 3, 6, 9, 8, 1]—
8range_min(3, 7)1
9range_add(0, 7, -2)[3, -1, 8, 1, 4, 7, 6, -1]—
10range_sum(2, 6)26
11range_min(0, 7)−1
12range_max(5, 7)7
13range_sum(4, 4)4

Row 7 is the trap for sqrt decomposition: element 5 sits in a block that may carry a lazy value, so the stored value must be 9 - lazy, not 9. Row 9 is the trap for the segment tree: a whole-array add is applied lazily at the root, and every later query must see it.

Then the stress test: for each , 1,500 random operations (more if you like; the reference uses this size so all four languages finish in seconds), comparing every engine with the oracle after every query.

Reference solution

Try Parts 1–5 yourself first. The reference implements all four engines in each language with the acceptance sequence and the stress test, using the same deterministic generator (MINSTD, x = x * 48271 mod (2^31 - 1), seed 2024) so the operation streams match across languages. It contains correctness asserts only; benchmarking code is left to you.

Reference solution: the range-query engine in four languages
import math


class Brute:
    """The oracle: obviously correct, O(n) per operation."""
    supports_min_max = True

    def __init__(self, a: list[int]):
        self.a = list(a)

    def point_set(self, i: int, v: int) -> None:
        self.a[i] = v

    def range_add(self, l: int, r: int, d: int) -> None:
        for i in range(l, r + 1):
            self.a[i] += d

    def range_sum(self, l: int, r: int) -> int:
        return sum(self.a[l:r + 1])

    def range_min(self, l: int, r: int) -> int:
        return min(self.a[l:r + 1])

    def range_max(self, l: int, r: int) -> int:
        return max(self.a[l:r + 1])


class LazySegTree:
    """Range add + range sum/min/max, O(log n) each."""
    supports_min_max = True

    def __init__(self, a: list[int]):
        self.n = len(a)
        size = 4 * max(1, self.n)
        self.sm, self.mn, self.mx, self.lz = [0] * size, [0] * size, [0] * size, [0] * size
        self._build(1, 0, self.n - 1, a)

    def _build(self, x, l, r, a):
        if l == r:
            self.sm[x] = self.mn[x] = self.mx[x] = a[l]
            return
        m = (l + r) // 2
        self._build(2 * x, l, m, a)
        self._build(2 * x + 1, m + 1, r, a)
        self._pull(x)

    def _pull(self, x):
        a, b = 2 * x, 2 * x + 1
        self.sm[x] = self.sm[a] + self.sm[b]
        self.mn[x] = min(self.mn[a], self.mn[b])
        self.mx[x] = max(self.mx[a], self.mx[b])

    def _apply(self, x, l, r, d):
        self.sm[x] += d * (r - l + 1)
        self.mn[x] += d
        self.mx[x] += d
        self.lz[x] += d

    def _push(self, x, l, r):
        if self.lz[x]:
            m = (l + r) // 2
            self._apply(2 * x, l, m, self.lz[x])
            self._apply(2 * x + 1, m + 1, r, self.lz[x])
            self.lz[x] = 0

    def _add(self, x, l, r, ql, qr, d):
        if qr < l or r < ql:
            return
        if ql <= l and r <= qr:
            self._apply(x, l, r, d)
            return
        self._push(x, l, r)
        m = (l + r) // 2
        self._add(2 * x, l, m, ql, qr, d)
        self._add(2 * x + 1, m + 1, r, ql, qr, d)
        self._pull(x)

    def _query(self, x, l, r, ql, qr):
        if ql <= l and r <= qr:
            return self.sm[x], self.mn[x], self.mx[x]
        self._push(x, l, r)
        m = (l + r) // 2
        if qr <= m:
            return self._query(2 * x, l, m, ql, qr)
        if ql > m:
            return self._query(2 * x + 1, m + 1, r, ql, qr)
        s1, n1, x1 = self._query(2 * x, l, m, ql, qr)
        s2, n2, x2 = self._query(2 * x + 1, m + 1, r, ql, qr)
        return s1 + s2, min(n1, n2), max(x1, x2)

    def range_add(self, l, r, d):
        self._add(1, 0, self.n - 1, l, r, d)

    def point_set(self, i, v):
        self.range_add(i, i, v - self.range_sum(i, i))

    def range_sum(self, l, r):
        return self._query(1, 0, self.n - 1, l, r)[0]

    def range_min(self, l, r):
        return self._query(1, 0, self.n - 1, l, r)[1]

    def range_max(self, l, r):
        return self._query(1, 0, self.n - 1, l, r)[2]


class Fenwick:
    """Range add + range sum with two BITs. No min/max under arbitrary updates."""
    supports_min_max = False

    def __init__(self, a: list[int]):
        self.n = len(a)
        self.b1, self.b2 = [0] * (self.n + 1), [0] * (self.n + 1)
        for i, v in enumerate(a):
            self.range_add(i, i, v)

    def _upd(self, b, i, d):              # i is 0-based
        i += 1
        while i <= self.n:
            b[i] += d
            i += i & -i

    def _pre(self, b, i):                 # b[1] + ... + b[i]
        s = 0
        while i > 0:
            s += b[i]
            i -= i & -i
        return s

    def _prefix(self, i):                 # a[0] + ... + a[i-1]
        return self._pre(self.b1, i) * i - self._pre(self.b2, i)

    def range_add(self, l, r, d):
        self._upd(self.b1, l, d)
        self._upd(self.b1, r + 1, -d)
        self._upd(self.b2, l, d * l)
        self._upd(self.b2, r + 1, -d * (r + 1))

    def point_set(self, i, v):
        self.range_add(i, i, v - self.range_sum(i, i))

    def range_sum(self, l, r):
        return self._prefix(r + 1) - self._prefix(l)

    def range_min(self, l, r):
        raise NotImplementedError("Fenwick tree: min needs invertible updates")

    def range_max(self, l, r):
        raise NotImplementedError("Fenwick tree: max needs invertible updates")


class SqrtDecomp:
    """Blocks of size ~sqrt(n) with a lazy add per block. O(sqrt n) per operation."""
    supports_min_max = True

    def __init__(self, a: list[int]):
        self.n = len(a)
        self.B = max(1, math.isqrt(self.n))
        nb = (self.n + self.B - 1) // self.B
        self.a = list(a)
        self.lz, self.bs, self.bmn, self.bmx = [0] * nb, [0] * nb, [0] * nb, [0] * nb
        for b in range(nb):
            self._rebuild(b)

    def _rebuild(self, b):                # block stats exclude the block's lazy value
        seg = self.a[b * self.B:min(self.n, (b + 1) * self.B)]
        self.bs[b], self.bmn[b], self.bmx[b] = sum(seg), min(seg), max(seg)

    def range_add(self, l, r, d):
        B = self.B
        bl, br = l // B, r // B
        if bl == br:
            for i in range(l, r + 1):
                self.a[i] += d
            self._rebuild(bl)
            return
        for i in range(l, (bl + 1) * B):
            self.a[i] += d
        self._rebuild(bl)
        for b in range(bl + 1, br):
            self.lz[b] += d
        for i in range(br * B, r + 1):
            self.a[i] += d
        self._rebuild(br)

    def point_set(self, i, v):
        b = i // self.B
        self.a[i] = v - self.lz[b]
        self._rebuild(b)

    def _query(self, l, r):
        B, a, lz = self.B, self.a, self.lz
        s, mn, mx = 0, math.inf, -math.inf
        bl, br = l // B, r // B
        if bl == br:
            for i in range(l, r + 1):
                v = a[i] + lz[bl]
                s, mn, mx = s + v, min(mn, v), max(mx, v)
            return s, mn, mx
        for i in range(l, (bl + 1) * B):
            v = a[i] + lz[bl]
            s, mn, mx = s + v, min(mn, v), max(mx, v)
        for b in range(bl + 1, br):
            s += self.bs[b] + lz[b] * B
            mn, mx = min(mn, self.bmn[b] + lz[b]), max(mx, self.bmx[b] + lz[b])
        for i in range(br * B, r + 1):
            v = a[i] + lz[br]
            s, mn, mx = s + v, min(mn, v), max(mx, v)
        return s, mn, mx

    def range_sum(self, l, r):
        return self._query(l, r)[0]

    def range_min(self, l, r):
        return self._query(l, r)[1]

    def range_max(self, l, r):
        return self._query(l, r)[2]


def acceptance(cls) -> None:
    e = cls([5, -2, 7, 0, 3, -4, 8, 1])
    mm = cls.supports_min_max
    assert e.range_sum(0, 7) == 18
    if mm:
        assert e.range_min(2, 5) == -4 and e.range_max(0, 3) == 7
    e.range_add(1, 4, 3)                  # [5, 1, 10, 3, 6, -4, 8, 1]
    assert e.range_sum(0, 3) == 19
    if mm:
        assert e.range_max(1, 5) == 10
    e.point_set(5, 9)                     # [5, 1, 10, 3, 6, 9, 8, 1]
    if mm:
        assert e.range_min(3, 7) == 1
    e.range_add(0, 7, -2)                 # [3, -1, 8, 1, 4, 7, 6, -1]
    assert e.range_sum(2, 6) == 26
    if mm:
        assert e.range_min(0, 7) == -1 and e.range_max(5, 7) == 7
    assert e.range_sum(4, 4) == 4


seed = 2024


def rnd(k: int) -> int:
    global seed
    seed = seed * 48271 % 2147483647
    return seed % k


def stress(n: int, steps: int) -> None:
    a = [rnd(2001) - 1000 for _ in range(n)]
    oracle = Brute(a)
    engines = [LazySegTree(a), Fenwick(a), SqrtDecomp(a)]
    for _ in range(steps):
        op = rnd(5)
        l = rnd(n)
        r = l + rnd(n - l)
        if op == 0:
            v = rnd(2001) - 1000
            oracle.point_set(l, v)
            for e in engines:
                e.point_set(l, v)
        elif op == 1:
            d = rnd(201) - 100
            oracle.range_add(l, r, d)
            for e in engines:
                e.range_add(l, r, d)
        elif op == 2:
            want = oracle.range_sum(l, r)
            for e in engines:
                assert e.range_sum(l, r) == want, (type(e).__name__, n, l, r)
        else:
            q = "range_min" if op == 3 else "range_max"
            want = getattr(oracle, q)(l, r)
            for e in engines:
                if e.supports_min_max:
                    assert getattr(e, q)(l, r) == want, (type(e).__name__, q, n, l, r)


for cls in (Brute, LazySegTree, Fenwick, SqrtDecomp):
    acceptance(cls)
try:
    Fenwick([1, 2]).range_min(0, 1)
    raise AssertionError("Fenwick min should be unsupported")
except NotImplementedError:
    pass
for n in (1, 2, 3, 10, 37, 100):
    stress(n, 1500)
print("range-query engine: all checks passed")
import java.util.List;

public class RangeQueryEngine {
    interface RangeEngine {
        void pointSet(int i, long v);
        void rangeAdd(int l, int r, long d);
        long sum(int l, int r);
        long min(int l, int r);
        long max(int l, int r);
        default boolean supportsMinMax() { return true; }
    }

    /** The oracle: obviously correct, O(n) per operation. */
    static final class Brute implements RangeEngine {
        private final long[] a;
        Brute(long[] a) { this.a = a.clone(); }
        public void pointSet(int i, long v) { a[i] = v; }
        public void rangeAdd(int l, int r, long d) { for (int i = l; i <= r; i++) a[i] += d; }
        public long sum(int l, int r) { long s = 0; for (int i = l; i <= r; i++) s += a[i]; return s; }
        public long min(int l, int r) { long m = Long.MAX_VALUE; for (int i = l; i <= r; i++) m = Math.min(m, a[i]); return m; }
        public long max(int l, int r) { long m = Long.MIN_VALUE; for (int i = l; i <= r; i++) m = Math.max(m, a[i]); return m; }
    }

    /** Range add + range sum/min/max, O(log n) each. */
    static final class LazySegTree implements RangeEngine {
        private final int n;
        private final long[] sm, mn, mx, lz;
        private long qs, qmn, qmx;               // query accumulators

        LazySegTree(long[] a) {
            n = a.length;
            int size = 4 * Math.max(1, n);
            sm = new long[size]; mn = new long[size]; mx = new long[size]; lz = new long[size];
            build(1, 0, n - 1, a);
        }

        private void build(int x, int l, int r, long[] a) {
            if (l == r) { sm[x] = mn[x] = mx[x] = a[l]; return; }
            int m = (l + r) >>> 1;
            build(2 * x, l, m, a);
            build(2 * x + 1, m + 1, r, a);
            pull(x);
        }

        private void pull(int x) {
            sm[x] = sm[2 * x] + sm[2 * x + 1];
            mn[x] = Math.min(mn[2 * x], mn[2 * x + 1]);
            mx[x] = Math.max(mx[2 * x], mx[2 * x + 1]);
        }

        private void apply(int x, int l, int r, long d) {
            sm[x] += d * (r - l + 1);
            mn[x] += d;
            mx[x] += d;
            lz[x] += d;
        }

        private void push(int x, int l, int r) {
            if (lz[x] != 0) {
                int m = (l + r) >>> 1;
                apply(2 * x, l, m, lz[x]);
                apply(2 * x + 1, m + 1, r, lz[x]);
                lz[x] = 0;
            }
        }

        private void add(int x, int l, int r, int ql, int qr, long d) {
            if (qr < l || r < ql) return;
            if (ql <= l && r <= qr) { apply(x, l, r, d); return; }
            push(x, l, r);
            int m = (l + r) >>> 1;
            add(2 * x, l, m, ql, qr, d);
            add(2 * x + 1, m + 1, r, ql, qr, d);
            pull(x);
        }

        private void query(int x, int l, int r, int ql, int qr) {
            if (qr < l || r < ql) return;
            if (ql <= l && r <= qr) {
                qs += sm[x]; qmn = Math.min(qmn, mn[x]); qmx = Math.max(qmx, mx[x]);
                return;
            }
            push(x, l, r);
            int m = (l + r) >>> 1;
            query(2 * x, l, m, ql, qr);
            query(2 * x + 1, m + 1, r, ql, qr);
        }

        private void run(int l, int r) {
            qs = 0; qmn = Long.MAX_VALUE; qmx = Long.MIN_VALUE;
            query(1, 0, n - 1, l, r);
        }

        public void rangeAdd(int l, int r, long d) { add(1, 0, n - 1, l, r, d); }
        public void pointSet(int i, long v) { rangeAdd(i, i, v - sum(i, i)); }
        public long sum(int l, int r) { run(l, r); return qs; }
        public long min(int l, int r) { run(l, r); return qmn; }
        public long max(int l, int r) { run(l, r); return qmx; }
    }

    /** Range add + range sum with two BITs. No min/max under arbitrary updates. */
    static final class Fenwick implements RangeEngine {
        private final int n;
        private final long[] b1, b2;

        Fenwick(long[] a) {
            n = a.length;
            b1 = new long[n + 1];
            b2 = new long[n + 1];
            for (int i = 0; i < n; i++) rangeAdd(i, i, a[i]);
        }

        private void upd(long[] b, int i, long d) { for (i++; i <= n; i += i & -i) b[i] += d; }
        private long pre(long[] b, int i) { long s = 0; for (; i > 0; i -= i & -i) s += b[i]; return s; }
        private long prefix(int i) { return pre(b1, i) * i - pre(b2, i); }

        public void rangeAdd(int l, int r, long d) {
            upd(b1, l, d);
            upd(b1, r + 1, -d);
            upd(b2, l, d * l);
            upd(b2, r + 1, -d * (r + 1));
        }
        public void pointSet(int i, long v) { rangeAdd(i, i, v - sum(i, i)); }
        public long sum(int l, int r) { return prefix(r + 1) - prefix(l); }
        public long min(int l, int r) { throw new UnsupportedOperationException("Fenwick: no min"); }
        public long max(int l, int r) { throw new UnsupportedOperationException("Fenwick: no max"); }
        public boolean supportsMinMax() { return false; }
    }

    /** Blocks of size ~sqrt(n) with a lazy add per block. O(sqrt n) per operation. */
    static final class SqrtDecomp implements RangeEngine {
        private final int n, bsz;
        private final long[] a, lz, bs, bmn, bmx;
        private long qs, qmn, qmx;

        SqrtDecomp(long[] init) {
            n = init.length;
            bsz = Math.max(1, (int) Math.sqrt(n));
            int nb = (n + bsz - 1) / bsz;
            a = init.clone();
            lz = new long[nb]; bs = new long[nb]; bmn = new long[nb]; bmx = new long[nb];
            for (int b = 0; b < nb; b++) rebuild(b);
        }

        private void rebuild(int b) {                // block stats exclude the lazy value
            long s = 0, lo = Long.MAX_VALUE, hi = Long.MIN_VALUE;
            for (int i = b * bsz; i < Math.min(n, (b + 1) * bsz); i++) {
                s += a[i]; lo = Math.min(lo, a[i]); hi = Math.max(hi, a[i]);
            }
            bs[b] = s; bmn[b] = lo; bmx[b] = hi;
        }

        public void rangeAdd(int l, int r, long d) {
            int bl = l / bsz, br = r / bsz;
            if (bl == br) {
                for (int i = l; i <= r; i++) a[i] += d;
                rebuild(bl);
                return;
            }
            for (int i = l; i < (bl + 1) * bsz; i++) a[i] += d;
            rebuild(bl);
            for (int b = bl + 1; b < br; b++) lz[b] += d;
            for (int i = br * bsz; i <= r; i++) a[i] += d;
            rebuild(br);
        }

        public void pointSet(int i, long v) {
            int b = i / bsz;
            a[i] = v - lz[b];
            rebuild(b);
        }

        private void take(long v) { qs += v; qmn = Math.min(qmn, v); qmx = Math.max(qmx, v); }

        private void run(int l, int r) {
            qs = 0; qmn = Long.MAX_VALUE; qmx = Long.MIN_VALUE;
            int bl = l / bsz, br = r / bsz;
            if (bl == br) {
                for (int i = l; i <= r; i++) take(a[i] + lz[bl]);
                return;
            }
            for (int i = l; i < (bl + 1) * bsz; i++) take(a[i] + lz[bl]);
            for (int b = bl + 1; b < br; b++) {
                qs += bs[b] + lz[b] * bsz;
                qmn = Math.min(qmn, bmn[b] + lz[b]);
                qmx = Math.max(qmx, bmx[b] + lz[b]);
            }
            for (int i = br * bsz; i <= r; i++) take(a[i] + lz[br]);
        }

        public long sum(int l, int r) { run(l, r); return qs; }
        public long min(int l, int r) { run(l, r); return qmn; }
        public long max(int l, int r) { run(l, r); return qmx; }
    }

    static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }

    static void acceptance(RangeEngine e, String name) {
        boolean mm = e.supportsMinMax();
        check(e.sum(0, 7) == 18, name + " #1");
        if (mm) check(e.min(2, 5) == -4 && e.max(0, 3) == 7, name + " #2-3");
        e.rangeAdd(1, 4, 3);
        check(e.sum(0, 3) == 19, name + " #5");
        if (mm) check(e.max(1, 5) == 10, name + " #6");
        e.pointSet(5, 9);
        if (mm) check(e.min(3, 7) == 1, name + " #8");
        e.rangeAdd(0, 7, -2);
        check(e.sum(2, 6) == 26, name + " #10");
        if (mm) check(e.min(0, 7) == -1 && e.max(5, 7) == 7, name + " #11-12");
        check(e.sum(4, 4) == 4, name + " #13");
    }

    static long seed = 2024;
    static int rnd(int k) { seed = seed * 48271 % 2147483647L; return (int) (seed % k); }

    static void stress(int n, int steps) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = rnd(2001) - 1000;
        Brute oracle = new Brute(a);
        List<RangeEngine> engines = List.of(new LazySegTree(a), new Fenwick(a), new SqrtDecomp(a));
        for (int s = 0; s < steps; s++) {
            int op = rnd(5);
            int l = rnd(n);
            int r = l + rnd(n - l);
            if (op == 0) {
                long v = rnd(2001) - 1000;
                oracle.pointSet(l, v);
                for (RangeEngine e : engines) e.pointSet(l, v);
            } else if (op == 1) {
                long d = rnd(201) - 100;
                oracle.rangeAdd(l, r, d);
                for (RangeEngine e : engines) e.rangeAdd(l, r, d);
            } else {
                for (RangeEngine e : engines) {
                    String where = e.getClass().getSimpleName() + " op=" + op + " n=" + n + " l=" + l + " r=" + r;
                    if (op == 2) check(e.sum(l, r) == oracle.sum(l, r), where);
                    else if (e.supportsMinMax()) {
                        if (op == 3) check(e.min(l, r) == oracle.min(l, r), where);
                        else check(e.max(l, r) == oracle.max(l, r), where);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        long[] init = {5, -2, 7, 0, 3, -4, 8, 1};
        acceptance(new Brute(init), "Brute");
        acceptance(new LazySegTree(init), "LazySegTree");
        acceptance(new Fenwick(init), "Fenwick");
        acceptance(new SqrtDecomp(init), "SqrtDecomp");
        boolean threw = false;
        try { new Fenwick(new long[] {1, 2}).min(0, 1); } catch (UnsupportedOperationException ex) { threw = true; }
        check(threw, "Fenwick min should be unsupported");
        for (int n : new int[] {1, 2, 3, 10, 37, 100}) stress(n, 1500);
        System.out.println("range-query engine: all checks passed");
    }
}
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <limits>
#include <memory>
#include <stdexcept>
#include <string>
#include <vector>

using ll = long long;
constexpr ll INF = std::numeric_limits<ll>::max();
constexpr ll NEG_INF = std::numeric_limits<ll>::min();

struct RangeEngine {
    virtual ~RangeEngine() = default;
    virtual void pointSet(int i, ll v) = 0;
    virtual void rangeAdd(int l, int r, ll d) = 0;
    virtual ll sum(int l, int r) = 0;
    virtual ll min(int l, int r) = 0;
    virtual ll max(int l, int r) = 0;
    virtual bool supportsMinMax() const { return true; }
    virtual std::string name() const = 0;
};

// The oracle: obviously correct, O(n) per operation.
struct Brute : RangeEngine {
    std::vector<ll> a;
    explicit Brute(std::vector<ll> init) : a(std::move(init)) {}
    void pointSet(int i, ll v) override { a[i] = v; }
    void rangeAdd(int l, int r, ll d) override { for (int i = l; i <= r; i++) a[i] += d; }
    ll sum(int l, int r) override { ll s = 0; for (int i = l; i <= r; i++) s += a[i]; return s; }
    ll min(int l, int r) override { return *std::min_element(a.begin() + l, a.begin() + r + 1); }
    ll max(int l, int r) override { return *std::max_element(a.begin() + l, a.begin() + r + 1); }
    std::string name() const override { return "Brute"; }
};

// Range add + range sum/min/max, O(log n) each.
struct LazySegTree : RangeEngine {
    int n;
    std::vector<ll> sm, mn, mx, lz;
    ll qs = 0, qmn = INF, qmx = NEG_INF;

    explicit LazySegTree(const std::vector<ll>& a) : n(static_cast<int>(a.size())) {
        std::size_t size = 4 * std::max(1, n);
        sm.assign(size, 0); mn.assign(size, 0); mx.assign(size, 0); lz.assign(size, 0);
        build(1, 0, n - 1, a);
    }
    void build(int x, int l, int r, const std::vector<ll>& a) {
        if (l == r) { sm[x] = mn[x] = mx[x] = a[l]; return; }
        int m = (l + r) / 2;
        build(2 * x, l, m, a);
        build(2 * x + 1, m + 1, r, a);
        pull(x);
    }
    void pull(int x) {
        sm[x] = sm[2 * x] + sm[2 * x + 1];
        mn[x] = std::min(mn[2 * x], mn[2 * x + 1]);
        mx[x] = std::max(mx[2 * x], mx[2 * x + 1]);
    }
    void apply(int x, int l, int r, ll d) {
        sm[x] += d * (r - l + 1);
        mn[x] += d;
        mx[x] += d;
        lz[x] += d;
    }
    void push(int x, int l, int r) {
        if (lz[x] != 0) {
            int m = (l + r) / 2;
            apply(2 * x, l, m, lz[x]);
            apply(2 * x + 1, m + 1, r, lz[x]);
            lz[x] = 0;
        }
    }
    void add(int x, int l, int r, int ql, int qr, ll d) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) { apply(x, l, r, d); return; }
        push(x, l, r);
        int m = (l + r) / 2;
        add(2 * x, l, m, ql, qr, d);
        add(2 * x + 1, m + 1, r, ql, qr, d);
        pull(x);
    }
    void query(int x, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            qs += sm[x]; qmn = std::min(qmn, mn[x]); qmx = std::max(qmx, mx[x]);
            return;
        }
        push(x, l, r);
        int m = (l + r) / 2;
        query(2 * x, l, m, ql, qr);
        query(2 * x + 1, m + 1, r, ql, qr);
    }
    void run(int l, int r) { qs = 0; qmn = INF; qmx = NEG_INF; query(1, 0, n - 1, l, r); }

    void rangeAdd(int l, int r, ll d) override { add(1, 0, n - 1, l, r, d); }
    void pointSet(int i, ll v) override { rangeAdd(i, i, v - sum(i, i)); }
    ll sum(int l, int r) override { run(l, r); return qs; }
    ll min(int l, int r) override { run(l, r); return qmn; }
    ll max(int l, int r) override { run(l, r); return qmx; }
    std::string name() const override { return "LazySegTree"; }
};

// Range add + range sum with two BITs. No min/max under arbitrary updates.
struct Fenwick : RangeEngine {
    int n;
    std::vector<ll> b1, b2;

    explicit Fenwick(const std::vector<ll>& a) : n(static_cast<int>(a.size())), b1(n + 1), b2(n + 1) {
        for (int i = 0; i < n; i++) rangeAdd(i, i, a[i]);
    }
    void upd(std::vector<ll>& b, int i, ll d) { for (i++; i <= n; i += i & -i) b[i] += d; }
    ll pre(const std::vector<ll>& b, int i) const { ll s = 0; for (; i > 0; i -= i & -i) s += b[i]; return s; }
    ll prefix(int i) const { return pre(b1, i) * i - pre(b2, i); }

    void rangeAdd(int l, int r, ll d) override {
        upd(b1, l, d);
        upd(b1, r + 1, -d);
        upd(b2, l, d * l);
        upd(b2, r + 1, -d * (r + 1));
    }
    void pointSet(int i, ll v) override { rangeAdd(i, i, v - sum(i, i)); }
    ll sum(int l, int r) override { return prefix(r + 1) - prefix(l); }
    ll min(int, int) override { throw std::logic_error("Fenwick: no min"); }
    ll max(int, int) override { throw std::logic_error("Fenwick: no max"); }
    bool supportsMinMax() const override { return false; }
    std::string name() const override { return "Fenwick"; }
};

// Blocks of size ~sqrt(n) with a lazy add per block. O(sqrt n) per operation.
struct SqrtDecomp : RangeEngine {
    int n, bsz;
    std::vector<ll> a, lz, bs, bmn, bmx;
    ll qs = 0, qmn = INF, qmx = NEG_INF;

    explicit SqrtDecomp(const std::vector<ll>& init)
        : n(static_cast<int>(init.size())),
          bsz(std::max(1, static_cast<int>(std::sqrt(static_cast<double>(init.size()))))),
          a(init) {
        int nb = (n + bsz - 1) / bsz;
        lz.assign(nb, 0); bs.assign(nb, 0); bmn.assign(nb, 0); bmx.assign(nb, 0);
        for (int b = 0; b < nb; b++) rebuild(b);
    }
    void rebuild(int b) {                       // block stats exclude the lazy value
        ll s = 0, lo = INF, hi = NEG_INF;
        for (int i = b * bsz; i < std::min(n, (b + 1) * bsz); i++) {
            s += a[i]; lo = std::min(lo, a[i]); hi = std::max(hi, a[i]);
        }
        bs[b] = s; bmn[b] = lo; bmx[b] = hi;
    }
    void rangeAdd(int l, int r, ll d) override {
        int bl = l / bsz, br = r / bsz;
        if (bl == br) {
            for (int i = l; i <= r; i++) a[i] += d;
            rebuild(bl);
            return;
        }
        for (int i = l; i < (bl + 1) * bsz; i++) a[i] += d;
        rebuild(bl);
        for (int b = bl + 1; b < br; b++) lz[b] += d;
        for (int i = br * bsz; i <= r; i++) a[i] += d;
        rebuild(br);
    }
    void pointSet(int i, ll v) override {
        int b = i / bsz;
        a[i] = v - lz[b];
        rebuild(b);
    }
    void take(ll v) { qs += v; qmn = std::min(qmn, v); qmx = std::max(qmx, v); }
    void run(int l, int r) {
        qs = 0; qmn = INF; qmx = NEG_INF;
        int bl = l / bsz, br = r / bsz;
        if (bl == br) {
            for (int i = l; i <= r; i++) take(a[i] + lz[bl]);
            return;
        }
        for (int i = l; i < (bl + 1) * bsz; i++) take(a[i] + lz[bl]);
        for (int b = bl + 1; b < br; b++) {
            qs += bs[b] + lz[b] * bsz;
            qmn = std::min(qmn, bmn[b] + lz[b]);
            qmx = std::max(qmx, bmx[b] + lz[b]);
        }
        for (int i = br * bsz; i <= r; i++) take(a[i] + lz[br]);
    }
    ll sum(int l, int r) override { run(l, r); return qs; }
    ll min(int l, int r) override { run(l, r); return qmn; }
    ll max(int l, int r) override { run(l, r); return qmx; }
    std::string name() const override { return "SqrtDecomp"; }
};

void check(bool ok, const std::string& msg) { if (!ok) throw std::runtime_error(msg); }

void acceptance(RangeEngine& e) {
    bool mm = e.supportsMinMax();
    check(e.sum(0, 7) == 18, e.name() + " #1");
    if (mm) check(e.min(2, 5) == -4 && e.max(0, 3) == 7, e.name() + " #2-3");
    e.rangeAdd(1, 4, 3);
    check(e.sum(0, 3) == 19, e.name() + " #5");
    if (mm) check(e.max(1, 5) == 10, e.name() + " #6");
    e.pointSet(5, 9);
    if (mm) check(e.min(3, 7) == 1, e.name() + " #8");
    e.rangeAdd(0, 7, -2);
    check(e.sum(2, 6) == 26, e.name() + " #10");
    if (mm) check(e.min(0, 7) == -1 && e.max(5, 7) == 7, e.name() + " #11-12");
    check(e.sum(4, 4) == 4, e.name() + " #13");
}

std::uint64_t seed = 2024;
int rnd(int k) { seed = seed * 48271 % 2147483647ULL; return static_cast<int>(seed % k); }

void stress(int n, int steps) {
    std::vector<ll> a(n);
    for (auto& x : a) x = rnd(2001) - 1000;
    Brute oracle(a);
    std::vector<std::unique_ptr<RangeEngine>> engines;
    engines.push_back(std::make_unique<LazySegTree>(a));
    engines.push_back(std::make_unique<Fenwick>(a));
    engines.push_back(std::make_unique<SqrtDecomp>(a));
    for (int s = 0; s < steps; s++) {
        int op = rnd(5);
        int l = rnd(n);
        int r = l + rnd(n - l);
        if (op == 0) {
            ll v = rnd(2001) - 1000;
            oracle.pointSet(l, v);
            for (auto& e : engines) e->pointSet(l, v);
        } else if (op == 1) {
            ll d = rnd(201) - 100;
            oracle.rangeAdd(l, r, d);
            for (auto& e : engines) e->rangeAdd(l, r, d);
        } else {
            for (auto& e : engines) {
                std::string where = e->name() + " op=" + std::to_string(op) + " n=" + std::to_string(n) +
                                    " l=" + std::to_string(l) + " r=" + std::to_string(r);
                if (op == 2) check(e->sum(l, r) == oracle.sum(l, r), where);
                else if (e->supportsMinMax()) {
                    if (op == 3) check(e->min(l, r) == oracle.min(l, r), where);
                    else check(e->max(l, r) == oracle.max(l, r), where);
                }
            }
        }
    }
}

int main() {
    std::vector<ll> init = {5, -2, 7, 0, 3, -4, 8, 1};
    Brute b(init);
    LazySegTree t(init);
    Fenwick f(init);
    SqrtDecomp q(init);
    acceptance(b); acceptance(t); acceptance(f); acceptance(q);
    bool threw = false;
    try { Fenwick({1, 2}).min(0, 1); } catch (const std::logic_error&) { threw = true; }
    check(threw, "Fenwick min should be unsupported");
    for (int n : {1, 2, 3, 10, 37, 100}) stress(n, 1500);
    std::cout << "range-query engine: all checks passed\n";
}
interface RangeEngine {
  readonly name: string;
  readonly supportsMinMax: boolean;
  pointSet(i: number, v: number): void;
  rangeAdd(l: number, r: number, d: number): void;
  sum(l: number, r: number): number;
  min(l: number, r: number): number;
  max(l: number, r: number): number;
}

// The oracle: obviously correct, O(n) per operation.
class Brute implements RangeEngine {
  readonly name = "Brute";
  readonly supportsMinMax = true;
  private a: number[];
  constructor(a: number[]) { this.a = [...a]; }
  pointSet(i: number, v: number): void { this.a[i] = v; }
  rangeAdd(l: number, r: number, d: number): void { for (let i = l; i <= r; i++) this.a[i] += d; }
  sum(l: number, r: number): number { let s = 0; for (let i = l; i <= r; i++) s += this.a[i]; return s; }
  min(l: number, r: number): number { return Math.min(...this.a.slice(l, r + 1)); }
  max(l: number, r: number): number { return Math.max(...this.a.slice(l, r + 1)); }
}

// Range add + range sum/min/max, O(log n) each.
class LazySegTree implements RangeEngine {
  readonly name = "LazySegTree";
  readonly supportsMinMax = true;
  private n: number;
  private sm: number[];
  private mn: number[];
  private mx: number[];
  private lz: number[];
  private qs = 0;
  private qmn = Infinity;
  private qmx = -Infinity;

  constructor(a: number[]) {
    this.n = a.length;
    const size = 4 * Math.max(1, this.n);
    this.sm = new Array(size).fill(0);
    this.mn = new Array(size).fill(0);
    this.mx = new Array(size).fill(0);
    this.lz = new Array(size).fill(0);
    this.build(1, 0, this.n - 1, a);
  }
  private build(x: number, l: number, r: number, a: number[]): void {
    if (l === r) { this.sm[x] = this.mn[x] = this.mx[x] = a[l]; return; }
    const m = (l + r) >> 1;
    this.build(2 * x, l, m, a);
    this.build(2 * x + 1, m + 1, r, a);
    this.pull(x);
  }
  private pull(x: number): void {
    this.sm[x] = this.sm[2 * x] + this.sm[2 * x + 1];
    this.mn[x] = Math.min(this.mn[2 * x], this.mn[2 * x + 1]);
    this.mx[x] = Math.max(this.mx[2 * x], this.mx[2 * x + 1]);
  }
  private apply(x: number, l: number, r: number, d: number): void {
    this.sm[x] += d * (r - l + 1);
    this.mn[x] += d;
    this.mx[x] += d;
    this.lz[x] += d;
  }
  private push(x: number, l: number, r: number): void {
    if (this.lz[x] !== 0) {
      const m = (l + r) >> 1;
      this.apply(2 * x, l, m, this.lz[x]);
      this.apply(2 * x + 1, m + 1, r, this.lz[x]);
      this.lz[x] = 0;
    }
  }
  private add(x: number, l: number, r: number, ql: number, qr: number, d: number): void {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { this.apply(x, l, r, d); return; }
    this.push(x, l, r);
    const m = (l + r) >> 1;
    this.add(2 * x, l, m, ql, qr, d);
    this.add(2 * x + 1, m + 1, r, ql, qr, d);
    this.pull(x);
  }
  private query(x: number, l: number, r: number, ql: number, qr: number): void {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
      this.qs += this.sm[x];
      this.qmn = Math.min(this.qmn, this.mn[x]);
      this.qmx = Math.max(this.qmx, this.mx[x]);
      return;
    }
    this.push(x, l, r);
    const m = (l + r) >> 1;
    this.query(2 * x, l, m, ql, qr);
    this.query(2 * x + 1, m + 1, r, ql, qr);
  }
  private run(l: number, r: number): void {
    this.qs = 0; this.qmn = Infinity; this.qmx = -Infinity;
    this.query(1, 0, this.n - 1, l, r);
  }
  rangeAdd(l: number, r: number, d: number): void { this.add(1, 0, this.n - 1, l, r, d); }
  pointSet(i: number, v: number): void { this.rangeAdd(i, i, v - this.sum(i, i)); }
  sum(l: number, r: number): number { this.run(l, r); return this.qs; }
  min(l: number, r: number): number { this.run(l, r); return this.qmn; }
  max(l: number, r: number): number { this.run(l, r); return this.qmx; }
}

// Range add + range sum with two BITs. No min/max under arbitrary updates.
class Fenwick implements RangeEngine {
  readonly name = "Fenwick";
  readonly supportsMinMax = false;
  private n: number;
  private b1: number[];
  private b2: number[];

  constructor(a: number[]) {
    this.n = a.length;
    this.b1 = new Array(this.n + 1).fill(0);
    this.b2 = new Array(this.n + 1).fill(0);
    a.forEach((v, i) => this.rangeAdd(i, i, v));
  }
  private upd(b: number[], i: number, d: number): void { for (i++; i <= this.n; i += i & -i) b[i] += d; }
  private pre(b: number[], i: number): number { let s = 0; for (; i > 0; i -= i & -i) s += b[i]; return s; }
  private prefix(i: number): number { return this.pre(this.b1, i) * i - this.pre(this.b2, i); }

  rangeAdd(l: number, r: number, d: number): void {
    this.upd(this.b1, l, d);
    this.upd(this.b1, r + 1, -d);
    this.upd(this.b2, l, d * l);
    this.upd(this.b2, r + 1, -d * (r + 1));
  }
  pointSet(i: number, v: number): void { this.rangeAdd(i, i, v - this.sum(i, i)); }
  sum(l: number, r: number): number { return this.prefix(r + 1) - this.prefix(l); }
  min(_l: number, _r: number): number { throw new Error("Fenwick: no min"); }
  max(_l: number, _r: number): number { throw new Error("Fenwick: no max"); }
}

// Blocks of size ~sqrt(n) with a lazy add per block. O(sqrt n) per operation.
class SqrtDecomp implements RangeEngine {
  readonly name = "SqrtDecomp";
  readonly supportsMinMax = true;
  private n: number;
  private bsz: number;
  private a: number[];
  private lz: number[];
  private bs: number[];
  private bmn: number[];
  private bmx: number[];
  private qs = 0;
  private qmn = Infinity;
  private qmx = -Infinity;

  constructor(init: number[]) {
    this.n = init.length;
    this.bsz = Math.max(1, Math.floor(Math.sqrt(this.n)));
    const nb = Math.ceil(this.n / this.bsz);
    this.a = [...init];
    this.lz = new Array(nb).fill(0);
    this.bs = new Array(nb).fill(0);
    this.bmn = new Array(nb).fill(0);
    this.bmx = new Array(nb).fill(0);
    for (let b = 0; b < nb; b++) this.rebuild(b);
  }
  private rebuild(b: number): void { // block stats exclude the lazy value
    let s = 0, lo = Infinity, hi = -Infinity;
    for (let i = b * this.bsz; i < Math.min(this.n, (b + 1) * this.bsz); i++) {
      s += this.a[i]; lo = Math.min(lo, this.a[i]); hi = Math.max(hi, this.a[i]);
    }
    this.bs[b] = s; this.bmn[b] = lo; this.bmx[b] = hi;
  }
  rangeAdd(l: number, r: number, d: number): void {
    const B = this.bsz, bl = Math.floor(l / B), br = Math.floor(r / B);
    if (bl === br) {
      for (let i = l; i <= r; i++) this.a[i] += d;
      this.rebuild(bl);
      return;
    }
    for (let i = l; i < (bl + 1) * B; i++) this.a[i] += d;
    this.rebuild(bl);
    for (let b = bl + 1; b < br; b++) this.lz[b] += d;
    for (let i = br * B; i <= r; i++) this.a[i] += d;
    this.rebuild(br);
  }
  pointSet(i: number, v: number): void {
    const b = Math.floor(i / this.bsz);
    this.a[i] = v - this.lz[b];
    this.rebuild(b);
  }
  private take(v: number): void { this.qs += v; this.qmn = Math.min(this.qmn, v); this.qmx = Math.max(this.qmx, v); }
  private run(l: number, r: number): void {
    this.qs = 0; this.qmn = Infinity; this.qmx = -Infinity;
    const B = this.bsz, bl = Math.floor(l / B), br = Math.floor(r / B);
    if (bl === br) {
      for (let i = l; i <= r; i++) this.take(this.a[i] + this.lz[bl]);
      return;
    }
    for (let i = l; i < (bl + 1) * B; i++) this.take(this.a[i] + this.lz[bl]);
    for (let b = bl + 1; b < br; b++) {
      this.qs += this.bs[b] + this.lz[b] * B;
      this.qmn = Math.min(this.qmn, this.bmn[b] + this.lz[b]);
      this.qmx = Math.max(this.qmx, this.bmx[b] + this.lz[b]);
    }
    for (let i = br * B; i <= r; i++) this.take(this.a[i] + this.lz[br]);
  }
  sum(l: number, r: number): number { this.run(l, r); return this.qs; }
  min(l: number, r: number): number { this.run(l, r); return this.qmn; }
  max(l: number, r: number): number { this.run(l, r); return this.qmx; }
}

function check(ok: boolean, msg: string): void {
  if (!ok) throw new Error(msg);
}

function acceptance(e: RangeEngine): void {
  const mm = e.supportsMinMax;
  check(e.sum(0, 7) === 18, `${e.name} #1`);
  if (mm) check(e.min(2, 5) === -4 && e.max(0, 3) === 7, `${e.name} #2-3`);
  e.rangeAdd(1, 4, 3);
  check(e.sum(0, 3) === 19, `${e.name} #5`);
  if (mm) check(e.max(1, 5) === 10, `${e.name} #6`);
  e.pointSet(5, 9);
  if (mm) check(e.min(3, 7) === 1, `${e.name} #8`);
  e.rangeAdd(0, 7, -2);
  check(e.sum(2, 6) === 26, `${e.name} #10`);
  if (mm) check(e.min(0, 7) === -1 && e.max(5, 7) === 7, `${e.name} #11-12`);
  check(e.sum(4, 4) === 4, `${e.name} #13`);
}

let seed = 2024;
function rnd(k: number): number {
  seed = (seed * 48271) % 2147483647;
  return seed % k;
}

function stress(n: number, steps: number): void {
  const a = Array.from({ length: n }, () => rnd(2001) - 1000);
  const oracle = new Brute(a);
  const engines: RangeEngine[] = [new LazySegTree(a), new Fenwick(a), new SqrtDecomp(a)];
  for (let s = 0; s < steps; s++) {
    const op = rnd(5);
    const l = rnd(n);
    const r = l + rnd(n - l);
    if (op === 0) {
      const v = rnd(2001) - 1000;
      oracle.pointSet(l, v);
      for (const e of engines) e.pointSet(l, v);
    } else if (op === 1) {
      const d = rnd(201) - 100;
      oracle.rangeAdd(l, r, d);
      for (const e of engines) e.rangeAdd(l, r, d);
    } else {
      for (const e of engines) {
        const where = `${e.name} op=${op} n=${n} l=${l} r=${r}`;
        if (op === 2) check(e.sum(l, r) === oracle.sum(l, r), where);
        else if (e.supportsMinMax) {
          if (op === 3) check(e.min(l, r) === oracle.min(l, r), where);
          else check(e.max(l, r) === oracle.max(l, r), where);
        }
      }
    }
  }
}

const init = [5, -2, 7, 0, 3, -4, 8, 1];
for (const e of [new Brute(init), new LazySegTree(init), new Fenwick(init), new SqrtDecomp(init)]) acceptance(e);
let threw = false;
try { new Fenwick([1, 2]).min(0, 1); } catch { threw = true; }
check(threw, "Fenwick min should be unsupported");
for (const n of [1, 2, 3, 10, 37, 100]) stress(n, 1500);
console.log("range-query engine: all checks passed");

What the numbers should look like

These are measurements of the reference implementations on one Windows laptop (C++ built with MSVC /O2, Python 3.14), uniformly random ranges, best of five runs for C++ and a single run of 20,000 operations for Python. Your absolute numbers will differ; the shape is what to compare.

C++, nanoseconds per operation ( operations per run):

Segment tree: buildSegment tree: sum mixSegment tree: min/max mixFenwick: buildFenwick: sum mixSqrt: buildSqrt: sum mixSqrt: min/max mix
0.2 ms4203890.2 ms550.01 ms172167
3.7 ms6156083.7 ms780.3 ms461449
36 ms1,05798164 ms1862.6 ms1,4781,385

Python, microseconds per operation:

Segment treeFenwickSqrt decompositionOracle
193.81249
294.836564

What to notice:

  • The Fenwick tree wins the sum workload by 5–8×, even though a range add is four tree walks. Each walk is a tight loop over a flat array with no recursion and no branches beyond the loop test, and both trees are words. If your workload is sums only, nothing else in this module comes close.
  • Sqrt decomposition beats the segment tree at small . At , and , yet the block version is about 2.5× faster in C++. Its inner loops scan contiguous memory, which the CPU prefetches and vectorises, while the recursive segment tree pays a function call, a push and a pull at each of about nodes and jumps around a -element array. The crossover in these measurements falls between and . In Python the effect is stronger, because sum() and min() over a slice run in C: sqrt decomposition still wins at there.
  • Growth rates do show up, eventually. From to the segment tree slows by about 2.5× (more levels, and the tree falls out of cache), sqrt decomposition by about 8.5× ( predicted). Asymptotics predict the trend; constants decide the winner at your .
  • Builds are cheap. Every structure builds a million elements in well under 0.1 s. The Fenwick build is the slowest at because the reference calls range_add per element, ; stretch goal 1 makes it . In Python the same build takes about 0.4 s at , which is when that optimisation starts to matter.
  • The oracle is the cost of not knowing this module: about 20× slower than the segment tree at in Python, and the gap grows roughly linearly with .

If your numbers disagree sharply — for example, sqrt decomposition slower than the oracle, or the segment tree slower at than at — look for a benchmark bug first: operations generated inside the timed loop, the oracle sharing state with another engine, or a JIT that has not warmed up.

Stretch goals

  1. builds. Build the Fenwick tree in linear time: copy the array into the tree, then for each add tree[i] into tree[i + (i & -i)]. For the range-add version, build from the difference array and from diff[i] * i. Measure the build-time drop.
  2. Range assign. Add range_set(l, r, v). In the segment tree this needs a second lazy tag (assign) that overrides pending adds when it is pushed — composition order matters, and the stress test will tell you when you got it wrong. In sqrt decomposition, a block-level "assigned value" flag does the job. The Fenwick tree cannot support it; extend the capability flags.
  3. Iterative (bottom-up) segment tree. Rewrite the segment tree without recursion, with the tree in an array of size . For point updates and range queries it is typically several times faster; adding lazy propagation to it is a good exercise in reasoning about the order of pushes.
  4. Tune the block size. Run the block-size sweep and explain the optimum: the cost of a query is about , minimised at , which differs from when per-element work () and per-block work () cost different amounts.
  5. A query planner. Give the engine a choose(workload) function that inspects which operations a workload needs and picks the fastest structure that supports them — Fenwick for sum-only, segment tree when min/max with range updates appear. That is a toy version of what a database query planner does when it chooses between index types.
  6. 2-D. Extend to a 2-D Fenwick tree for point updates and rectangle sums, and compare with a 2-D prefix-sum table that is rebuilt on every update.

Further reading

Module 3 navigation. Previous: Spatial Trees. Module overview: Trees. Course home: DSA: Zero to Mastery.