Prefix Sums, Fenwick Trees and Segment Trees
Answer many range queries fast. Prefix sums and difference arrays, a sparse table for minimums, a Fenwick tree, and segment trees over any monoid with lazy propagation, all stress tested.
Many questions about one array
A weather station logs rainfall for n = 200,000 days, and analysts send q = 200,000 questions of the form "how much rain fell from day l to day r?". Summing each range directly costs up to n additions per question, 4*10^10 in the worst case. With the constraints table from Complexity in Practice, that is hopeless; O((n + q) log n) or better is the target.
The right structure depends on two questions. Does the array change between queries? And what is being combined: sums (which can be subtracted), minimums (which cannot, but do not mind overlap), or something more general? This lesson builds the answers in increasing order of power and cost:
- Prefix sums for a fixed array:
O(n)once,O(1)per sum query. Difference arrays for the reverse, many range updates and one final read. - A sparse table for a fixed array and an operation like
min:O(1)per query afterO(n log n)preprocessing. - A Fenwick tree when values change:
O(log n)per update and per prefix sum, in a dozen lines. - A segment tree for any associative operation, with lazy propagation when whole ranges change at once.
Each one is stress tested against a plain array, the slowest and most obviously correct structure there is, following the habit from Fast I/O, Contest Templates and Stress Testing. The next lesson, String Algorithms, applies the same "precompute once, answer fast" idea to text, with the prefix function and prefix hashes.
Prefix sums: pay once, answer by subtraction
Let pre[i] = a[1] + ... + a[i] with pre[0] = 0. Then the sum of a[l..r] is pre[r] - pre[l - 1]: everything up to r, minus everything before l. The extra pre[0] slot is what makes l = 1 work without a special case.
The same idea works in two dimensions. With P[i][j] the sum of the top-left i by j block, inclusion-exclusion gives the sum of any rectangle from four lookups: add the big block, subtract the strip above and the strip to the left, and add back the corner that was subtracted twice.
The difference array runs the idea backwards. To add v to every element of a[l..r], record +v at l and -v at r + 1. After all updates, one running sum over the difference array rebuilds the array. Each update is O(1); the price is that you cannot read the array in between without rebuilding it.
The program answers three rainfall queries from an embedded input (on a judge, solve(std::cin, std::cout)), sums one rectangle of a park grid, and applies three range updates. The input is n and q, the daily amounts, then q pairs l r, 1-indexed and inclusive:
8 3
3 0 5 2 0 0 7 1
1 8
3 4
5 6#include <iostream>
#include <print>
#include <sstream>
#include <vector>
using ll = long long;
// Queries "total rainfall from day l to day r" (1-indexed, inclusive).
void solve(std::istream& in, std::ostream& out) {
int n, q;
in >> n >> q;
std::vector<ll> pre(n + 1, 0); // pre[i] = a[1] + ... + a[i], pre[0] = 0
for (int i = 1; i <= n; ++i) {
ll x;
in >> x;
pre[i] = pre[i - 1] + x;
}
while (q--) {
int l, r;
in >> l >> r;
out << pre[r] - pre[l - 1] << '\n';
}
}
int main() {
std::istringstream in("8 3\n3 0 5 2 0 0 7 1\n1 8\n3 4\n5 6\n");
solve(in, std::cout);
// 2D: trees per cell of a park; P[i][j] = sum of the top-left i x j block.
std::vector<std::vector<int>> park{{1, 0, 2, 0}, {0, 3, 0, 1}, {4, 0, 0, 2}};
int rows = 3, cols = 4;
std::vector<std::vector<ll>> P(rows + 1, std::vector<ll>(cols + 1, 0));
for (int i = 1; i <= rows; ++i)
for (int j = 1; j <= cols; ++j)
P[i][j] = park[i - 1][j - 1] + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1];
auto block = [&](int r1, int c1, int r2, int c2) { // rows r1..r2, cols c1..c2
return P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1];
};
std::println("trees in rows 2..3, cols 2..4: {}", block(2, 2, 3, 4));
// Difference array: add v to a[l..r] in O(1), rebuild once at the end.
std::vector<ll> diff(10 + 1, 0); // positions 0..9, one spare slot
auto addRange = [&](int l, int r, ll v) { diff[l] += v, diff[r + 1] -= v; };
addRange(2, 5, 10);
addRange(4, 9, 1);
addRange(0, 0, 7);
ll running = 0;
std::print("after the updates:");
for (int i = 0; i < 10; ++i) std::print(" {}", running += diff[i]);
std::println("");
}Press Run to compile and run this example.
18
7
0
trees in rows 2..3, cols 2..4: 6
after the updates: 7 0 10 10 11 11 1 1 1 1The rectangle covers 3 0 1 and 0 0 2, which is 6. The difference array needed the spare slot at index 10 for the update that ends at 9; without it, diff[r + 1] writes past the end. Use long long for prefix sums by default: 2*10^5 values of up to 10^9 add up to 2*10^14, far beyond int.
Sparse table: `O(1)` minimums when overlap is harmless
Prefix sums work because subtraction undoes addition. There is no way to "subtract" a minimum, so range minimum needs another idea. Precompute the minimum of every block whose length is a power of two: up[k][i] is the minimum of a[i .. i + 2^k - 1], and up[k][i] is the smaller of two blocks of length 2^(k-1). That is about log2 n rows of n entries, O(n log n) time and memory.
A query [l, r] of length len takes the largest k with 2^k <= len and combines two blocks: one starting at l, one ending at r. Together they cover the range, and they usually overlap. For min the overlap does not matter, since min(x, x) = x. Operations with that property (min, max, gcd, bitwise and and or) are called idempotent, and for them the query is two lookups: O(1). For a sum, the overlap is counted twice.
std::bit_width(x) (C++20, header <bit>, unsigned types only) is the number of bits needed for x, so std::bit_width(len) - 1 is the floor of log2(len). The program builds the table once with min and once with +, and stress tests both against a direct fold.
#include <algorithm>
#include <bit>
#include <cstdint>
#include <print>
#include <vector>
struct Lcg {
std::uint64_t s;
std::uint32_t next() {
s = s * 6364136223846793005ULL + 1442695040888963407ULL;
return std::uint32_t(s >> 33);
}
int range(int lo, int hi) { return lo + int(next() % std::uint32_t(hi - lo + 1)); }
};
// up[k][i] = op over a[i .. i + 2^k - 1]. O(1) queries are only right when
// op(x, x) == x (min, max, gcd, and, or): the two halves may overlap.
template <class Op>
struct SparseTable {
std::vector<std::vector<int>> up;
Op op;
long long buildSteps = 0;
SparseTable(const std::vector<int>& a, Op f) : up{a}, op(f) {
for (int k = 1; (1 << k) <= int(a.size()); ++k) {
const auto& prev = up[k - 1];
std::vector<int> row(a.size() - (1 << k) + 1);
for (std::size_t i = 0; i < row.size(); ++i, ++buildSteps)
row[i] = op(prev[i], prev[i + (1 << (k - 1))]);
up.push_back(std::move(row));
}
}
int query(int l, int r) const { // inclusive, l <= r
int k = std::bit_width(unsigned(r - l + 1)) - 1; // largest 2^k <= length
return op(up[k][l], up[k][r - (1 << k) + 1]);
}
};
int main() {
std::vector<int> a{5, 2, 8, 6, 3, 7, 1, 4};
SparseTable minTable(a, [](int x, int y) { return std::min(x, y); });
std::println("min of a[1..5] = {}", minTable.query(1, 5));
for (const char* name : {"min", "sum"}) {
bool isMin = name[0] == 'm';
Lcg rng{9};
int checked = 0;
for (; checked < 3000; ++checked) {
std::vector<int> v(rng.range(1, 20));
for (int& x : v) x = rng.range(-50, 50);
auto f = [isMin](int x, int y) { return isMin ? std::min(x, y) : x + y; };
SparseTable table(v, f);
int l = rng.range(0, int(v.size()) - 1), r = rng.range(l, int(v.size()) - 1);
int slow = v[l];
for (int i = l + 1; i <= r; ++i) slow = f(slow, v[i]);
if (table.query(l, r) != slow) {
std::println("{}: wrong on case {}, range [{}, {}]: got {}, want {}",
name, checked, l, r, table.query(l, r), slow);
break;
}
}
if (checked == 3000)
std::println("{}: {} random cases, all agree", name, checked);
}
for (int n : {1'000, 100'000}) {
auto smaller = [](int x, int y) { return std::min(x, y); };
SparseTable t(std::vector<int>(n, 1), smaller);
std::println("n = {:>6}: {} build steps, {} rows", n, t.buildSteps, t.up.size());
}
}Press Run to compile and run this example.
min of a[1..5] = 2
min: 3000 random cases, all agree
sum: wrong on case 0, range [3, 3]: got -62, want -31
n = 1000: 7987 build steps, 10 rows
n = 100000: 1468946 build steps, 17 rowsThe query [1, 5] has length 5, so k = 2 and the two blocks are a[1..4] and a[2..5], overlapping in three elements. For a sum, even a single element [3, 3] goes wrong: both "halves" are the same element, so it is counted twice. The build counts grow like n log2 n (1,468,946 is a little under 100,000 * 16, one entry per position in each of the 16 rows after the first), and once built, every query is two lookups no matter how long the range. The limitation is that the table is static: changing one value invalidates every block that contains it, 2^k entries in row k and O(n) in total.
Fenwick tree: prefix sums that survive updates
When values change between queries, prefix sums break: one update changes up to n of them. The Fenwick tree (also called a binary indexed tree, published by Peter Fenwick in 1994) stores a cleverly chosen set of partial sums so that both an update and a prefix sum touch only O(log n) of them.
The trick is the lowest set bit of an index, lowbit(i) = i & -i. In two's complement, -i is ~i + 1: inverting the bits and adding one turns the lowest 1-bit of i back into a 1 and clears everything above it that i had, so i & -i keeps exactly that bit. For i = 12 = 1100 in binary, -i ends in 0100, and lowbit(12) = 4.
Using 1-based indices, t[i] stores the sum of the lowbit(i) elements ending at i, that is a[i - lowbit(i) + 1 .. i]. So t[12] holds a[9..12], t[8] holds a[1..8] and every odd t[i] holds just a[i].
- Prefix sum up to
i: addt[i], then jump toi - lowbit(i), the index just before the blockt[i]covered, untilireaches 0. Fori = 13 = 1101:t[13]coversa[13..13], thent[12]coversa[9..12], thent[8]coversa[1..8]. Each jump clears one bit, so there are at mostlog2 n + 1steps. - Update at
i: everyt[j]whose block containsimust change. They are found by jumpingi += lowbit(i):5 → 6 → 8 → 16 → .... Each jump moves the lowest set bit up, so againO(log n)steps.
A range sum is two prefix sums. As an application, the program counts inversions (pairs i < j with a[i] > a[j]): walk left to right, and for each value ask the tree how many earlier values are not larger, after compressing the values to ranks 1..m. That is O(n log n) instead of O(n^2).
#include <algorithm>
#include <cstdint>
#include <print>
#include <vector>
using ll = long long;
struct Lcg {
std::uint64_t s;
std::uint32_t next() {
s = s * 6364136223846793005ULL + 1442695040888963407ULL;
return std::uint32_t(s >> 33);
}
int range(int lo, int hi) { return lo + int(next() % std::uint32_t(hi - lo + 1)); }
};
// 1-indexed: t[i] holds the sum of a[i - lowbit(i) + 1 .. i], lowbit(i) = i & -i.
struct Fenwick {
std::vector<ll> t;
explicit Fenwick(int n) : t(n + 1, 0) {}
void add(int i, ll delta) { // a[i] += delta, 1 <= i <= n
for (; i < int(t.size()); i += i & -i) t[i] += delta;
}
ll prefix(int i) const { // a[1] + ... + a[i], 0 <= i <= n
ll sum = 0;
for (; i > 0; i -= i & -i) sum += t[i];
return sum;
}
ll range(int l, int r) const { return prefix(r) - prefix(l - 1); }
};
// Pairs i < j with a[i] > a[j]: for each value, count larger values seen before it.
ll inversions(const std::vector<int>& a) {
std::vector<int> sorted = a; // compress values to ranks 1..m
std::ranges::sort(sorted);
sorted.erase(std::ranges::unique(sorted).begin(), sorted.end());
Fenwick seen(int(sorted.size()));
ll count = 0;
for (std::size_t j = 0; j < a.size(); ++j) {
int rank = int(std::ranges::lower_bound(sorted, a[j]) - sorted.begin()) + 1;
count += ll(j) - seen.prefix(rank); // seen so far, minus those <= a[j]
seen.add(rank, 1);
}
return count;
}
int main() {
Fenwick f(8);
for (int i = 1; i <= 8; ++i) f.add(i, i * 10); // a = 10 20 ... 80
f.add(3, 5);
std::println("a[2..4] = {}, a[1..8] = {}", f.range(2, 4), f.range(1, 8));
std::println("inversions of 3 1 4 1 5 9 2 6: {}",
inversions({3, 1, 4, 1, 5, 9, 2, 6}));
Lcg rng{12};
int checked = 0;
for (; checked < 3000; ++checked) {
int n = rng.range(1, 12);
Fenwick fw(n);
std::vector<ll> naive(n + 1, 0);
for (int op = 0; op < 20; ++op) {
int l = rng.range(1, n), r = rng.range(l, n);
if (rng.range(0, 1)) {
ll d = rng.range(-9, 9);
fw.add(l, d), naive[l] += d;
} else {
ll slow = 0;
for (int i = l; i <= r; ++i) slow += naive[i];
if (fw.range(l, r) != slow) {
std::println("mismatch at case {}", checked);
return 1;
}
}
}
std::vector<int> a(rng.range(0, 10));
for (int& x : a) x = rng.range(1, 5); // many equal values
ll slow = 0;
for (std::size_t i = 0; i < a.size(); ++i)
for (std::size_t j = i + 1; j < a.size(); ++j) slow += a[i] > a[j];
if (inversions(a) != slow) {
std::println("inversions mismatch at case {}", checked);
return 1;
}
}
std::println("{} random cases, all agree", checked);
int n = 1'000'000, worstAdd = 0, worstPrefix = 0; // the cost of one operation
for (int start = 1; start <= n; ++start) {
int steps = 0;
for (int j = start; j <= n; j += j & -j) ++steps;
worstAdd = std::max(worstAdd, steps);
steps = 0;
for (int j = start; j > 0; j -= j & -j) ++steps;
worstPrefix = std::max(worstPrefix, steps);
}
std::println("n = {}: at most {} steps per add, {} per prefix",
n, worstAdd, worstPrefix);
// 0-indexed by mistake: 0 & -0 is 0, so add(0, ...) never moves.
int i = 0, steps = 0;
for (; i < 9 && steps < 1000; i += i & -i) ++steps;
std::println("add starting at index 0: still at {} after {} steps", i, steps);
}Press Run to compile and run this example.
a[2..4] = 95, a[1..8] = 365
inversions of 3 1 4 1 5 9 2 6: 8
3000 random cases, all agree
n = 1000000: at most 20 steps per add, 19 per prefix
add starting at index 0: still at 0 after 1000 stepsa[2..4] = 20 + 35 + 40, with the 5 added to a[3]. The stress test mixes updates and queries on small arrays and checks inversion counts on arrays full of equal values, where < versus <= mistakes show up. Over every starting index up to 10^6, no update takes more than 20 steps and no prefix query more than 19, which is log2(10^6) rounded up and down. The last line is the bug the 1-based convention exists to avoid: at index 0, i & -i is 0, so the update loop never advances and the program hangs. If your data is 0-indexed, add 1 when you call the tree, in one place.
A segment tree over any monoid
A Fenwick tree answers prefix queries, and a range is a difference of two prefixes. That needs an inverse: it works for sums and xor, not for minimum, and not for "compose these functions in order". A segment tree needs no inverse. Each node stores the combination of a contiguous block, the root covers everything, and each node's block is split between its two children. Any range is the union of O(log n) nodes, and a point update changes the O(log n) nodes on one leaf-to-root path.
What does the segment tree need from the operation? Exactly two things: it must be associative, combine(combine(a, b), c) == combine(a, combine(b, c)), so that blocks can be grouped in any way; and it must have an identity e with combine(e, x) == x == combine(x, e), to start a query that has collected nothing yet. A set with such an operation is called a monoid. Commutativity is not required, as long as the code keeps the left part on the left.
A C++20 concept writes the requirement down so that the compiler checks it at the point of use. It checks only syntax (that M::identity() and M::combine(a, b) exist and return M::Value); associativity and the identity law remain your promise, which the stress test checks.
The tree below is the compact bottom-up layout described in a 2015 Codeforces blog post by Al.Cash ("Efficient and easy segment trees"): 2n entries, leaves at t[n..2n-1], and node i combining 2i and 2i + 1. A query walks the two ends of the half-open range [l, r) upwards, collecting nodes from the left end into left and from the right end into right, so the order of elements is preserved. The program runs three monoids through the same stress test: minimum with the correct identity, minimum with identity 0 (a classic slip), and composition of affine maps x -> a*x + b, which is not commutative.
#include <algorithm>
#include <concepts>
#include <cstdint>
#include <limits>
#include <print>
#include <vector>
using ll = long long;
struct Lcg {
std::uint64_t s;
std::uint32_t next() {
s = s * 6364136223846793005ULL + 1442695040888963407ULL;
return std::uint32_t(s >> 33);
}
int range(int lo, int hi) { return lo + int(next() % std::uint32_t(hi - lo + 1)); }
};
// A monoid: an associative combine with an identity element e (combine(e, x) == x).
template <class M>
concept Monoid = requires(typename M::Value a, typename M::Value b) {
{ M::identity() } -> std::same_as<typename M::Value>;
{ M::combine(a, b) } -> std::same_as<typename M::Value>;
};
struct MinMonoid {
using Value = ll;
static Value identity() { return std::numeric_limits<ll>::max(); }
static Value combine(Value a, Value b) { return std::min(a, b); }
};
struct BadMinMonoid : MinMonoid { // the classic slip: 0 is not neutral for min
static Value identity() { return 0; }
};
struct Affine { // x -> a*x + b mod p; combine(f, g) applies f first. Not commutative.
struct Value { ll a, b; bool operator==(const Value&) const = default; };
static constexpr ll kMod = 1'000'000'007;
static Value identity() { return {1, 0}; }
static Value combine(Value f, Value g) {
return {g.a * f.a % kMod, (g.a * f.b + g.b) % kMod};
}
};
// Bottom-up segment tree: leaves at t[n..2n-1], node i combines 2i and 2i+1.
template <Monoid M>
struct SegTree {
using V = typename M::Value;
int n;
std::vector<V> t;
explicit SegTree(const std::vector<V>& a) : n(int(a.size())), t(2 * a.size()) {
std::ranges::copy(a, t.begin() + n);
for (int i = n - 1; i > 0; --i) t[i] = M::combine(t[2 * i], t[2 * i + 1]);
}
void set(int p, V value) {
for (t[p += n] = value; p > 1; p /= 2) t[p / 2] = M::combine(t[p & ~1], t[p | 1]);
}
V query(int l, int r) const { // combine of a[l..r), in order
V left = M::identity(), right = M::identity();
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l & 1) left = M::combine(left, t[l++]);
if (r & 1) right = M::combine(t[--r], right);
}
return M::combine(left, right);
}
};
template <Monoid M, class Gen>
void stress(const char* name, Gen gen) {
Lcg rng{77};
for (int test = 0; test < 2000; ++test) {
std::vector<typename M::Value> a(rng.range(1, 13)); // not just powers of two
for (auto& x : a) x = gen(rng);
SegTree<M> tree(a);
for (int op = 0; op < 10; ++op) {
int p = rng.range(0, int(a.size()) - 1);
a[p] = gen(rng), tree.set(p, a[p]);
int l = rng.range(0, int(a.size()) - 1), r = rng.range(l + 1, int(a.size()));
auto slow = a[l];
for (int i = l + 1; i < r; ++i) slow = M::combine(slow, a[i]);
if (!(tree.query(l, r) == slow)) {
std::println("{}: wrong on test {}", name, test);
return;
}
}
}
std::println("{}: 2000 tests, all agree", name);
}
int main() {
SegTree<MinMonoid> tree({5, 2, 8, 6, 3, 7, 1, 4});
tree.set(6, 9);
std::println("min of a[2..6) = {}, min of all = {}",
tree.query(2, 6), tree.query(0, 8));
auto positive = [](Lcg& r) { return ll(r.range(1, 100)); };
stress<MinMonoid>("min, identity = max ", positive);
stress<BadMinMonoid>("min, identity = 0 ", positive);
stress<Affine>("affine maps in order", [](Lcg& r) {
return Affine::Value{r.range(0, 9), r.range(0, 9)};
});
}Press Run to compile and run this example.
min of a[2..6) = 3, min of all = 2
min, identity = max : 2000 tests, all agree
min, identity = 0 : wrong on test 0
affine maps in order: 2000 tests, all agreeWith identity 0, every query over positive values returns 0, because the "nothing collected yet" value wins every comparison. It compiles, satisfies the concept and fails at once. The affine test matters for a different reason: composing maps is order-sensitive, so it would catch a query that combined the right-hand nodes in the wrong order, and it runs on sizes that are not powers of two. Writing SegTree<int> does not compile; the error names the unsatisfied Monoid constraint instead of pointing into the middle of the class.
Range updates with lazy propagation
Now the updates change whole ranges: "add x to every element in [l, r]", mixed with "sum of [l, r]". Updating each element is O(n) per operation. Lazy propagation does for updates what the segment tree does for queries: an update stops at the O(log n) nodes that exactly cover its range, applies the change to their stored sums, and leaves a tag ("my children still owe +x") instead of descending further. Whenever a later operation needs to go below a tagged node, it first pushes the tag to the two children.
This version is the recursive layout: node 1 is the root, node v has children 2v and 2v + 1, and 4n slots are enough for any n. For each node, sum[v] is already correct for its block, including its own tag; pending[v] is what its children have not received yet. After an update recurses into the children, the parent is recomputed from them, which is exactly where a forgotten push loses data: the children never received the parent's tag, so the recomputed sum silently drops it. The program shows that, then counts nodes visited per operation. The sample uses 0-indexed operations 1 l r x (add) and 2 l r (sum):
6 5
1 0 3 5
1 2 5 -2
2 0 5
2 3 4
2 5 5#include <algorithm>
#include <cstdint>
#include <iostream>
#include <print>
#include <sstream>
#include <vector>
using ll = long long;
struct Lcg {
std::uint64_t s;
std::uint32_t next() {
s = s * 6364136223846793005ULL + 1442695040888963407ULL;
return std::uint32_t(s >> 33);
}
int range(int lo, int hi) { return lo + int(next() % std::uint32_t(hi - lo + 1)); }
};
// Range add, range sum. Node v covers [lo, hi]; pending[v] is an addition already
// counted in sum[v] but not yet passed to v's children.
struct LazyTree {
int n;
std::vector<ll> sum, pending;
bool forgetPush = false; // to show the bug
long long visits = 0;
explicit LazyTree(int size) : n(size), sum(4 * size, 0), pending(4 * size, 0) {}
void apply(int v, int lo, int hi, ll add) {
sum[v] += add * (hi - lo + 1);
pending[v] += add;
}
void push(int v, int lo, int hi) {
if (pending[v] == 0) return;
int mid = (lo + hi) / 2;
apply(2 * v, lo, mid, pending[v]);
apply(2 * v + 1, mid + 1, hi, pending[v]);
pending[v] = 0;
}
void add(int l, int r, ll x, int v, int lo, int hi) {
++visits;
if (r < lo || hi < l) return;
if (l <= lo && hi <= r) { // fully covered: tag it and stop here
apply(v, lo, hi, x);
return;
}
if (!forgetPush) push(v, lo, hi);
int mid = (lo + hi) / 2;
add(l, r, x, 2 * v, lo, mid);
add(l, r, x, 2 * v + 1, mid + 1, hi);
sum[v] = sum[2 * v] + sum[2 * v + 1]; // drops pending[v] if it was not pushed
}
ll total(int l, int r, int v, int lo, int hi) {
++visits;
if (r < lo || hi < l) return 0;
if (l <= lo && hi <= r) return sum[v];
push(v, lo, hi);
int mid = (lo + hi) / 2;
return total(l, r, 2 * v, lo, mid) + total(l, r, 2 * v + 1, mid + 1, hi);
}
void add(int l, int r, ll x) { add(l, r, x, 1, 0, n - 1); }
ll total(int l, int r) { return total(l, r, 1, 0, n - 1); }
};
// Input: n q, then "1 l r x" (add x to a[l..r]) or "2 l r" (print the sum), 0-indexed.
void solve(std::istream& in, std::ostream& out) {
int n, q;
in >> n >> q;
LazyTree tree(n);
while (q--) {
int type, l, r;
in >> type >> l >> r;
if (type == 1) {
ll x;
in >> x;
tree.add(l, r, x);
} else {
out << tree.total(l, r) << '\n';
}
}
}
int main() {
std::istringstream in("6 5\n1 0 3 5\n1 2 5 -2\n2 0 5\n2 3 4\n2 5 5\n");
solve(in, std::cout);
for (bool forget : {true, false}) {
Lcg rng{4};
int checked = 0;
for (; checked < 2000; ++checked) {
int n = rng.range(1, 10);
LazyTree tree(n);
tree.forgetPush = forget;
std::vector<ll> naive(n, 0);
bool ok = true;
for (int op = 0; op < 15 && ok; ++op) {
int l = rng.range(0, n - 1), r = rng.range(l, n - 1);
if (rng.range(0, 1)) {
ll x = rng.range(-5, 5);
tree.add(l, r, x);
for (int i = l; i <= r; ++i) naive[i] += x;
} else {
ll slow = 0;
for (int i = l; i <= r; ++i) slow += naive[i];
ok = tree.total(l, r) == slow;
}
}
if (!ok) break;
}
const char* name = forget ? "no push in add" : "with push ";
if (checked < 2000) std::println("{}: wrong on test {}", name, checked);
else std::println("{}: 2000 tests, all agree", name);
}
for (int n : {1'000, 100'000}) { // nodes visited per operation, worst over many
LazyTree tree(n);
Lcg rng{1};
long long worst = 0;
for (int op = 0; op < 2000; ++op) {
int l = rng.range(0, n - 1), r = rng.range(l, n - 1);
tree.visits = 0;
if (op % 2) tree.add(l, r, 1); else tree.total(l, r);
worst = std::max(worst, tree.visits);
}
std::println("n = {:>6}: at most {} nodes visited per operation", n, worst);
}
}Press Run to compile and run this example.
12
1
-2
no push in add: wrong on test 0
with push : 2000 tests, all agree
n = 1000: at most 39 nodes visited per operation
n = 100000: at most 67 nodes visited per operationAfter the two updates the array is 5 5 3 3 -2 -2, which gives the three sums. The visit counts stay within about 4 log2 n (log2(10^5) is about 17, and 4 * 17 = 68), because on each level of the tree at most four nodes are touched. The cost of an operation grows by a few nodes when n grows a hundredfold.
The tag and the stored value must agree on what "apply" means. For range add with range minimum instead of sum, apply would add x to the minimum (not x times the length). For range assignment, the tag must say "set to x", and a pending add arriving after a pending set has to be merged into one tag. Every new pair of update and query needs the same three decisions: how a tag changes a node's value, how two tags combine, and what "no tag" is.