Segment Tree and Fenwick Tree Quiz: C++ Practice Test
A timed practice test on segment trees and Fenwick trees: point updates, range queries, i & -i, inversion counting, and a range-add, range-sum program in C++.
- Course: Competitive Programming study plan
- Module: Segment trees and Fenwick trees
- Kind: Checkpoint — cleared at 70%
- Reading time: 60 min
- Runtime: Clang 18 · C++20
Checkpoint — Segment trees and Fenwick trees is the checkpoint that closes the Segment trees and Fenwick trees module: a graded quiz and whole-program exercises, passed at 70%.
Instructions
A timed checkpoint on the module: segment trees (build, point update, range query, the identity for an outside node), Fenwick trees (i & -i, the climb and the descent, ranges as two prefixes), counting with a tree indexed by value, and choosing between them and plain prefix sums.
How it works. Sixty minutes from the moment you start the timer: ten questions and one program. 70% on the questions and the program accepted clears the module.
Before you start, make sure you can answer these from memory:
- Which nodes a query for
[l, r]takes whole, and what an outside node returns for a sum and for a minimum. - What
i & -iis for 12, and which cellsadd(5, x)andsum(7)touch when n = 8. - Why a minimum query cannot be answered as
sum(r) − sum(l − 1). - How compressing values to ranks turns "earlier elements greater than x" into a prefix count.
The program is range add with range sum: two Fenwick trees, every value in long long.
Common questions
How do you support range add and range sum with Fenwick trees?
Keep two Fenwick trees B1 and B2. Adding x to [l, r] is four point updates: B1 gets +x at l and −x at r + 1, B2 gets +x·(l − 1) at l and −x·r at r + 1. The prefix sum up to i is then sum(B1, i) · i − sum(B2, i), and a range is a difference of two prefixes.
How many nodes does a segment tree need?
With the recursive layout (children 2v and 2v + 1, root 1), allocate 4n slots: the tree has at most 2·2^⌈log2 n⌉ − 1 nodes, which is below 4n for every n. A bottom-up iterative tree needs exactly 2n.
Exercise
Range add, range sum
Answer q operations on an array of n integers:
1 l r v— addvto everya[i]withl ≤ i ≤ r;2 l r— printa[l] + … + a[r].
Positions are 1-indexed. Use two Fenwick trees B1, B2: a range add is B1.add(l, v), B1.add(r+1, −v), B2.add(l, v·(l−1)), B2.add(r+1, −v·r), and the prefix sum up to i is B1.sum(i)·i − B2.sum(i) plus the original prefix.
Constraints: 1 ≤ n, q ≤ 2 × 10^5, |a[i]|, |v| ≤ 10^6. Input: n q, the values, then q lines. Output: one line per type-2 operation.
5 6
1 2 3 4 5
2 1 5
1 2 4 10
2 1 5
2 3 3
1 1 5 -1
2 4 5prints 15, 45, 13 and 17 on four lines.
In this module: Segment trees and Fenwick trees
← Segment trees and Fenwick trees · DP optimisations — prefix sums, a monotonic deque and bitmasks →