These are the notes for Competitive Programming episode 63. A Fenwick tree (binary indexed tree, BIT) stores in t[i] the sum of the last i & −i values ending at i; a prefix sum walks i −= i & −i, an update walks i += i & −i, both O(log n), in about ten lines. Rain Gauges needs range add, point read and range sum: a difference array turns a range add into two point updates, and a second Fenwick tree gives range sums with prefix(i) = sum1(i) · i − sum2(i). Passing the 0-based gauge numbers straight in calls add(0, x), where 0 & −0 = 0: an endless loop (TLE even on the sample). Pass the Parcel (the Josephus problem) needs "the k-th child still in the circle": erasing from a vector is TLE at n = 5 · 10^5, while a Fenwick tree of 0/1 flags finds the k-th by walking down powers of two in O(log n); writing <= instead of < lands one past (child 8 of 7). Stress tests pass. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The real-life hook
The weather office's register doesn't have one page per gauge. Page 8 holds the total of pages 1–8, page 6 the total of 5–6, page 7 just its own gauge. A storm from gauge l to r is recorded with two marks: +x at l and −x just after r. A gauge's reading is the sum of all marks up to it. And to find "the k-th child still in the game", an usher asks big questions first: do the first 256 seats hold fewer than k children? Then skip them all and continue.
How a Fenwick tree works
i & −iis the lowest set bit of i (two's complement): 6 = 110₂ → 2, 8 → 8, 7 → 1.t[i]= a[i − lowbit(i) + 1] + … + a[i].- Prefix sum to i: add
t[i], theni −= i & −i(drop the lowest bit), until 0. prefix(7) = t[7] + t[6] + t[4]. - Point add at i: add to
t[i], theni += i & −i(climb to the next block that contains i), while i ≤ n. Add at 3 touches t[3], t[4], t[8]. - Both loops run at most log₂ n + 1 times. 1-indexed only: with i = 0,
i & −i = 0and the update loop never ends.
t[8] = a1..a8
t[4] = a1..a4 t[6] = a5..a6
t[2] = a1..a2 t[3] t[5] t[7]
t[1]
Problem K1 · Rain Gauges
(Written for this course, in the style of a classic range update / range query problem.)
- Input: n q (n, q ≤ 5 · 10^5); gauges are numbered 0 to n − 1 and start at 0. Operations:
1 l r x(add x to gauges l..r),2 i(print gauge i),3 l r(print the total of l..r).
5 6
1 0 2 5
2 1
1 1 4 3
3 0 4
2 4
3 2 3
Answers: 5 27 3 11.
The obvious attempt: loops (TLE)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, q;
ll a[500001];
void rangeAdd(int l, int r, ll x) { for (int i = l; i <= r; i++) a[i] += x; }
ll point(int i) { return a[i]; }
ll total(int l, int r) {
ll s = 0;
for (int i = l; i <= r; i++) s += a[i];
return s;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
while (q--) {
int type;
cin >> type;
if (type == 1) {
int l, r;
ll x;
cin >> l >> r >> x;
rangeAdd(l, r, x);
} else if (type == 2) {
int i;
cin >> i;
cout << point(i) << "\n";
} else {
int l, r;
cin >> l >> r;
cout << total(l, r) << "\n";
}
}
}
5
27
3
11
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, q;
ll a[500001];
void rangeAdd(int l, int r, ll x) { for (int i = l; i <= r; i++) a[i] += x; }
ll point(int i) { return a[i]; }
ll total(int l, int r) {
ll s = 0;
for (int i = l; i <= r; i++) s += a[i];
return s;
}
int main() {
n = q = 500000;
mt19937 rng(63);
ll check = 0;
for (int i = 0; i < q; i++) {
int l = rng() % 10 + 1, r = n - rng() % 10; // almost everything
if (i % 2 == 0) rangeAdd(l, r, rng() % 1000);
else check ^= total(l, r);
}
cout << check << "\n";
}
Time Limit Exceeded
Range add, point read: one tree on the difference array
Let d be the difference array: a[i] = d[1] + … + d[i]. Adding x to a[l..r] changes only d[l] (+x) and d[r + 1] (−x). So a range add is two Fenwick updates, and a point read is a Fenwick prefix sum of d.
Range add, range sum: two trees
prefix(i) = a[1] + … + a[i] = Σ_{j ≤ i} d[j] · (i − j + 1) = i · Σ d[j] − Σ d[j] · (j − 1).
So keep b1 over d[j] and b2 over d[j] · (j − 1):
| Operation | b1 | b2 |
|---|---|---|
| add x to [l, r] | +x at l, −x at r + 1 | +x·(l − 1) at l, −x·r at r + 1 |
| point(i) | sum1(i) | |
| prefix(i) | sum1(i) · i − sum2(i) |
(At r + 1 the b2 mark is −x·r because d[r+1] = −x and (r + 1) − 1 = r.)
The bug: 0-based numbers straight into the tree
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, q;
ll b1[500002], b2[500002]; // two Fenwick trees, 1-indexed
void add(ll *b, int i, ll x) { for (; i <= n; i += i & -i) b[i] += x; }
ll sum(ll *b, int i) {
ll s = 0;
for (; i > 0; i -= i & -i) s += b[i];
return s;
}
void rangeAdd(int l, int r, ll x) { // two marks in each tree
add(b1, l, x), add(b1, r + 1, -x);
add(b2, l, x * (l - 1)), add(b2, r + 1, -x * r);
}
ll point(int i) { return sum(b1, i); } // the difference array, summed
ll prefix(int i) { return sum(b1, i) * i - sum(b2, i); }
ll total(int l, int r) { return prefix(r) - prefix(l - 1); }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
while (q--) {
int type;
cin >> type;
if (type == 1) {
int l, r;
ll x;
cin >> l >> r >> x;
rangeAdd(l, r, x);
} else if (type == 2) {
int i;
cin >> i;
cout << point(i) << "\n";
} else {
int l, r;
cin >> l >> r;
cout << total(l, r) << "\n";
}
}
}
Time Limit Exceeded
The very first storm starts at gauge 0, so add(b1, 0, 5) runs i += 0 & −0 forever. Shift to 1-based on input:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, q;
ll b1[500002], b2[500002]; // two Fenwick trees, 1-indexed
void add(ll *b, int i, ll x) { for (; i <= n; i += i & -i) b[i] += x; }
ll sum(ll *b, int i) {
ll s = 0;
for (; i > 0; i -= i & -i) s += b[i];
return s;
}
void rangeAdd(int l, int r, ll x) { // two marks in each tree
add(b1, l, x), add(b1, r + 1, -x);
add(b2, l, x * (l - 1)), add(b2, r + 1, -x * r);
}
ll point(int i) { return sum(b1, i); } // the difference array, summed
ll prefix(int i) { return sum(b1, i) * i - sum(b2, i); }
ll total(int l, int r) { return prefix(r) - prefix(l - 1); }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q; // gauges 0..n-1 -> 1..n
while (q--) {
int type;
cin >> type;
if (type == 1) {
int l, r;
ll x;
cin >> l >> r >> x;
rangeAdd(l + 1, r + 1, x);
} else if (type == 2) {
int i;
cin >> i;
cout << point(i + 1) << "\n";
} else {
int l, r;
cin >> l >> r;
cout << total(l + 1, r + 1) << "\n";
}
}
}
5
27
3
11
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, q;
ll b1[500002], b2[500002]; // two Fenwick trees, 1-indexed
void add(ll *b, int i, ll x) { for (; i <= n; i += i & -i) b[i] += x; }
ll sum(ll *b, int i) {
ll s = 0;
for (; i > 0; i -= i & -i) s += b[i];
return s;
}
void rangeAdd(int l, int r, ll x) { // two marks in each tree
add(b1, l, x), add(b1, r + 1, -x);
add(b2, l, x * (l - 1)), add(b2, r + 1, -x * r);
}
ll point(int i) { return sum(b1, i); } // the difference array, summed
ll prefix(int i) { return sum(b1, i) * i - sum(b2, i); }
ll total(int l, int r) { return prefix(r) - prefix(l - 1); }
int main() {
n = q = 500000;
mt19937 rng(63);
ll check = 0;
for (int i = 0; i < q; i++) {
int l = rng() % 10 + 1, r = n - rng() % 10; // almost everything
if (i % 2 == 0) rangeAdd(l, r, rng() % 1000);
else check ^= total(l, r);
}
cout << check << "\n";
}
60141812631868
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, q;
ll b1[500002], b2[500002]; // two Fenwick trees, 1-indexed
void add(ll *b, int i, ll x) { for (; i <= n; i += i & -i) b[i] += x; }
ll sum(ll *b, int i) {
ll s = 0;
for (; i > 0; i -= i & -i) s += b[i];
return s;
}
void rangeAdd(int l, int r, ll x) { // two marks in each tree
add(b1, l, x), add(b1, r + 1, -x);
add(b2, l, x * (l - 1)), add(b2, r + 1, -x * r);
}
ll point(int i) { return sum(b1, i); } // the difference array, summed
ll prefix(int i) { return sum(b1, i) * i - sum(b2, i); }
ll total(int l, int r) { return prefix(r) - prefix(l - 1); }
int main() {
mt19937 rng(63);
for (int t = 1; t <= 500; t++) {
n = rng() % 12 + 1;
fill(b1, b1 + n + 2, 0), fill(b2, b2 + n + 2, 0);
vector<ll> a(n + 1, 0);
for (int k = 0; k < 30; k++) {
int l = rng() % n + 1, r = rng() % n + 1;
if (l > r) swap(l, r);
ll x = (ll)(rng() % 21) - 10;
rangeAdd(l, r, x);
for (int i = l; i <= r; i++) a[i] += x;
int i = rng() % n + 1;
ll s = accumulate(a.begin() + l, a.begin() + r + 1, 0LL);
if (point(i) != a[i] || total(l, r) != s) { cout << "mismatch on test " << t; return 0; }
}
}
cout << "all 500 tests passed";
}
all 500 tests passed
Problem K2 · Pass the Parcel
(Written for this course; the classic Josephus problem.)
n children 1..n sit in a circle. Counting k children (the counting starts at the child after the last one who left), the k-th leaves. Print the order of leaving. n ≤ 5 · 10^5, k ≤ 10^9.
7 3
Order: 3 6 2 7 5 1 4.
The obvious attempt: erase from a vector (TLE)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, k;
int main() {
cin >> n >> k;
vector<int> circle(n);
iota(circle.begin(), circle.end(), 1);
int cur = 0;
while (!circle.empty()) {
cur = (cur + k - 1) % circle.size(); // count k children
cout << circle[cur] << " ";
circle.erase(circle.begin() + cur); // shifts everyone after
}
cout << "\n";
}
3 6 2 7 5 1 4
Each erase shifts every child after it: about n² / 4 moves.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, k;
int main() {
n = 500000, k = 1000; // half a million children
ll check = 0, step = 0;
vector<int> circle(n);
iota(circle.begin(), circle.end(), 1);
int cur = 0;
while (!circle.empty()) {
cur = (cur + k - 1) % circle.size(); // count k children
check += ++step * circle[cur];
circle.erase(circle.begin() + cur); // shifts everyone after
}
cout << check << "\n";
}
Time Limit Exceeded
Fenwick descent: the k-th one still in
Keep a Fenwick tree over flags (1 = still in). The rank of the next child to leave among those left is cur = (cur + k − 1) mod left. To find the child with rank k (1-based):
- pos = 0; for pw = the highest power of two ≤ n, then pw / 2, …, 1: if pos + pw ≤ n and
t[pos + pw] < k, the whole block (pos, pos + pw] holds fewer than k children, so skip it: pos += pw, k −= t[pos]. - The answer is pos + 1.
This works because pos is always a sum of larger powers of two, so the block that t[pos + pw] covers is exactly (pos, pos + pw]. One array read per step: O(log n), versus O(log² n) for a binary search over prefix sums.
The bug: <= instead of <
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, k, t[500001]; // t: Fenwick tree of "still in the circle"
void add(int i, int x) { for (; i <= n; i += i & -i) t[i] += x; }
int kth(int k) { // the k-th child still in
int pos = 0;
for (int pw = 1 << 19; pw; pw >>= 1) // 2^19 > 5·10^5
if (pos + pw <= n && t[pos + pw] <= k) { // whole block before the k-th?
pos += pw;
k -= t[pos];
}
return pos + 1;
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) add(i, 1);
int cur = 0;
for (int left = n; left > 0; left--) {
cur = (cur + k - 1) % left; // rank among those left
int who = kth(cur + 1);
add(who, -1);
cout << who << " ";
}
cout << "\n";
}
4 7 3 8 6 2 5
With <=, a block holding exactly k children is skipped too, so the search lands one past the k-th child: there is no child 8. With <:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, k, t[500001]; // t: Fenwick tree of "still in the circle"
void add(int i, int x) { for (; i <= n; i += i & -i) t[i] += x; }
int kth(int k) { // the k-th child still in
int pos = 0;
for (int pw = 1 << 19; pw; pw >>= 1) // 2^19 > 5·10^5
if (pos + pw <= n && t[pos + pw] < k) { // whole block before the k-th?
pos += pw;
k -= t[pos];
}
return pos + 1;
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) add(i, 1);
int cur = 0;
for (int left = n; left > 0; left--) {
cur = (cur + k - 1) % left; // rank among those left
int who = kth(cur + 1);
add(who, -1);
cout << who << " ";
}
cout << "\n";
}
3 6 2 7 5 1 4
1
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, k, t[500001]; // t: Fenwick tree of "still in the circle"
void add(int i, int x) { for (; i <= n; i += i & -i) t[i] += x; }
int kth(int k) { // the k-th child still in
int pos = 0;
for (int pw = 1 << 19; pw; pw >>= 1) // 2^19 > 5·10^5
if (pos + pw <= n && t[pos + pw] < k) { // whole block before the k-th?
pos += pw;
k -= t[pos];
}
return pos + 1;
}
int main() {
n = 500000, k = 1000; // half a million children
ll check = 0, step = 0;
for (int i = 1; i <= n; i++) add(i, 1);
int cur = 0;
for (int left = n; left > 0; left--) {
cur = (cur + k - 1) % left; // rank among those left
int who = kth(cur + 1);
add(who, -1);
check += ++step * who;
}
cout << check << "\n";
}
31255643113023472
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, k, t[500001]; // t: Fenwick tree of "still in the circle"
void add(int i, int x) { for (; i <= n; i += i & -i) t[i] += x; }
int kth(int k) { // the k-th child still in
int pos = 0;
for (int pw = 1 << 19; pw; pw >>= 1) // 2^19 > 5·10^5
if (pos + pw <= n && t[pos + pw] < k) { // whole block before the k-th?
pos += pw;
k -= t[pos];
}
return pos + 1;
}
int main() {
mt19937 rng(63);
for (int tc = 1; tc <= 500; tc++) {
n = rng() % 20 + 1, k = rng() % 30 + 1;
fill(t, t + n + 1, 0);
vector<int> circle(n);
iota(circle.begin(), circle.end(), 1);
for (int i = 1; i <= n; i++) add(i, 1);
int a = 0, b = 0;
for (int left = n; left > 0; left--) {
a = (a + k - 1) % circle.size();
int slow = circle[a];
circle.erase(circle.begin() + a);
b = (b + k - 1) % left;
int fast = kth(b + 1);
add(fast, -1);
if (slow != fast) { cout << "mismatch on test " << tc; return 0; }
}
}
cout << "all 500 tests passed";
}
all 500 tests passed
Complexity vs the constraints
| Method | Time | Verdict at 5 · 10^5 |
|---|---|---|
| K1: loops | O(n) per operation | TLE |
| K1: two Fenwick trees | O(log n) per operation, 2 · (n + 2) long long |
accepted |
| K2: vector erase | O(n²) | TLE |
| K2: binary search on prefix sums | O(n log² n) | accepted, slower |
| K2: Fenwick descent | O(n log n) | accepted |
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
add(0, x) (0-based input) |
Time Limit Exceeded |
0 & −0 = 0, i never grows |
1-indexed: i + 1 |
t[pos + pw] <= k |
4 7 3 8 6 2 5 (child 8!) |
lands one past the k-th | strictly < k |
starting pw below the highest bit of n |
wrong children for large n | can't reach big indexes | pw ≥ highest power of two ≤ n |
| arrays of size n | out of bounds at r + 1 | the second mark lands at n + 1 | size n + 2 |
b2 mark −x · (r + 1) |
wrong totals | the factor is (j − 1) = r | −x · r |
int sums |
overflow | up to 5 · 10^5 · 10^9 | long long |
| erasing from a vector | Time Limit Exceeded |
O(n) per erase | Fenwick of flags |
Mini project
Write a Fenwick struct with add(i, x), sum(i), rangeSum(l, r), kth(k) and a RangeFenwick (two trees) with rangeAdd(l, r, x), point(i), rangeSum(l, r). Test them against brute force with random operations including negative values, k = 1, k = size, and n = 1. Then use them for homework 1–4.
Practice
These are the four homework problems from the episode. Every answer below came from a compiled C++ program (g++ -O2 -std=c++17).
1. Count inversions (pairs i < j with a[i] > a[j]).
Solution
Scan left to right; before adding a[j], the number of earlier values greater than a[j] is j minus the number of earlier values ≤ a[j]. Compress the values first. O(n log n). Sample 3 1 4 1 5 2: 6 inversions.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() { // inversions: pairs i < j with a[i] > a[j]
int n;
cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
vector<int> vals(a);
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
int m = vals.size();
vector<int> t(m + 1, 0);
ll inv = 0;
for (int j = 0; j < n; j++) {
int id = lower_bound(vals.begin(), vals.end(), a[j]) - vals.begin() + 1; // 1..m
int seen = 0; // earlier values <= a[j]
for (int i = id; i > 0; i -= i & -i) seen += t[i];
inv += j - seen; // earlier values > a[j]
for (int i = id; i <= m; i += i & -i) t[i]++;
}
cout << inv << "\n";
}
6
2. The k-th smallest of a growing bag of numbers (1 x add x, 2 k print the k-th smallest).
Solution
Read all operations first, compress the added numbers, keep a Fenwick tree of counts and use the descent. O((q) log q).
#include <bits/stdc++.h>
using namespace std;
// Offline: "1 x" adds number x to the bag, "2 k" asks the k-th smallest in the bag.
int m, t[200001];
void add(int i) { for (; i <= m; i += i & -i) t[i]++; }
int kth(int k) {
int pos = 0;
for (int pw = 1 << 18; pw; pw >>= 1) // 2^18 > 2·10^5 values
if (pos + pw <= m && t[pos + pw] < k) pos += pw, k -= t[pos];
return pos + 1;
}
int main() {
int q;
cin >> q;
vector<pair<int, long long>> ops(q);
vector<long long> vals;
for (auto &[type, x] : ops) {
cin >> type >> x;
if (type == 1) vals.push_back(x);
}
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
m = vals.size();
for (auto [type, x] : ops) {
if (type == 1) add(lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1);
else cout << vals[kth(x) - 1] << "\n"; // compressed index -> the real number
}
}
10
30
30
3. 2D Fenwick tree (add v at cell (x, y), sum of a rectangle).
Solution
Nest the two loops; a rectangle is four prefix rectangles by inclusion-exclusion. O(log n · log m) per operation.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
ll t[1001][1001]; // 2D Fenwick: each dimension uses i & -i
void add(int x, int y, ll v) {
for (int i = x; i <= n; i += i & -i)
for (int j = y; j <= m; j += j & -j) t[i][j] += v;
}
ll sum(int x, int y) { // rectangle (1,1)..(x,y)
ll s = 0;
for (int i = x; i > 0; i -= i & -i)
for (int j = y; j > 0; j -= j & -j) s += t[i][j];
return s;
}
ll rect(int x1, int y1, int x2, int y2) {
return sum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) + sum(x1 - 1, y1 - 1);
}
int main() {
int q;
cin >> n >> m >> q;
while (q--) {
int type;
cin >> type;
if (type == 1) { int x, y; ll v; cin >> x >> y >> v; add(x, y, v); }
else { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; cout << rect(x1, y1, x2, y2) << "\n"; }
}
}
12
9
4. A queue: remove the person at position k; who is at position p now?
Solution
Flags for "still in the queue"; both operations are the k-th / p-th query. Sample: 6 people, remove position 2, ask position 2 (3), remove position 1, ask positions 1 (3) and 4 (6).
#include <bits/stdc++.h>
using namespace std;
// A queue of people 1..n. "1 k": the person at position k leaves. "2 p": who is at position p now?
int n, t[500001];
void add(int i, int x) { for (; i <= n; i += i & -i) t[i] += x; }
int kth(int k) {
int pos = 0;
for (int pw = 1 << 19; pw; pw >>= 1)
if (pos + pw <= n && t[pos + pw] < k) pos += pw, k -= t[pos];
return pos + 1;
}
int main() {
int q;
cin >> n >> q;
for (int i = 1; i <= n; i++) add(i, 1);
while (q--) {
int type, k;
cin >> type >> k;
int who = kth(k);
if (type == 1) add(who, -1);
else cout << who << "\n";
}
}
3
3
6
Quick quiz
13 = 1101₂. Which entries does prefix(13) read?
A) 13, 12, 8 · B) 13, 12, 4 · C) 13, 8 · D) 13, 11, 7
Answer
A. 13 − 1 = 12 (1100₂), 12 − 4 = 8 (1000₂), 8 − 8 = 0: t[13] + t[12] + t[8].
Interview questions
- What does
i & −icompute and why? The lowest set bit of i, because −i is the two's complement (~i + 1). - What does
t[i]store? The sum of the lowbit(i) values ending at i. - How do you do range add + point query with a BIT? A BIT over the difference array: +x at l, −x at r + 1; the point value is a prefix sum.
- And range add + range sum? Two BITs: prefix(i) = sum1(i)·i − sum2(i) with marks x and x·(l − 1).
- How do you find the k-th element in O(log n)? Walk down powers of two, skipping blocks whose count is less than k.
- Fenwick vs segment tree? Fenwick: shorter, faster, less memory, but only for invertible/prefix-friendly operations; segment trees handle min/max, assignment and custom merges.
- Why must a BIT be 1-indexed? Index 0 has no lowest set bit: the update loop would never advance.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Fenwick tree (BIT) | An array where t[i] sums the last lowbit(i) values | prefix sums |
Lowest set bit (i & −i) |
The smallest power of two in i's binary form | 12 → 4 |
| Two's complement | How negative integers are stored; −i = ~i + 1 | why i & −i works |
| Prefix sum | a[1] + … + a[i] | sum(i) |
| Point update | Change one value | add(i, x) |
| Difference array | d[i] = a[i] − a[i − 1]; a range add touches two entries | storms |
| Range add | Add x to a[l..r] | rangeAdd |
| 1-indexed | Positions start at 1 | Fenwick trees |
| Order statistic | The k-th smallest / k-th present element | the k-th child |
| Fenwick descent | Finding the k-th by walking down powers of two | kth(k) |
| Josephus problem | Every k-th person in a circle leaves | Pass the Parcel |
| Inversion | A pair i < j with a[i] > a[j] | homework 1 |
| Coordinate compression | Mapping values to 1..m by rank | homework 2 |
| 2D Fenwick tree | A Fenwick tree of Fenwick trees | homework 3 |
| Inclusion-exclusion | Rectangle = four prefix rectangles with signs | homework 3 |
| Stress test | Comparing a fast solution with a slow, surely-correct one on many random inputs | all 500 tests passed |
| Time Limit Exceeded (TLE) | Too slow (or never ends) | add(0, x) |
| Wrong Answer (WA) | A wrong output | child 8 |
| Sparse table | O(1) range minimum on a static array | next episode |
Summary
t[i]sums the last i & −i values; prefix:i −= i & −i; update:i += i & −i; 1-indexed (index 0 loops forever).- Range add = two marks on the difference array; range sum =
sum1(i) · i − sum2(i)with a second tree. - k-th element: walk down powers of two, skipping blocks with strictly fewer than k.
- Everything is O(log n) in about ten lines.
Solutions in C++, Java and Python
Problem K1 · Rain Gauges
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, q;
ll b1[500002], b2[500002]; // two Fenwick trees, 1-indexed
void add(ll *b, int i, ll x) { for (; i <= n; i += i & -i) b[i] += x; }
ll sum(ll *b, int i) {
ll s = 0;
for (; i > 0; i -= i & -i) s += b[i];
return s;
}
void rangeAdd(int l, int r, ll x) { // two marks in each tree
add(b1, l, x), add(b1, r + 1, -x);
add(b2, l, x * (l - 1)), add(b2, r + 1, -x * r);
}
ll point(int i) { return sum(b1, i); } // the difference array, summed
ll prefix(int i) { return sum(b1, i) * i - sum(b2, i); }
ll total(int l, int r) { return prefix(r) - prefix(l - 1); }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q; // gauges 0..n-1 -> 1..n
while (q--) {
int type;
cin >> type;
if (type == 1) {
int l, r;
ll x;
cin >> l >> r >> x;
rangeAdd(l + 1, r + 1, x);
} else if (type == 2) {
int i;
cin >> i;
cout << point(i + 1) << "\n";
} else {
int l, r;
cin >> l >> r;
cout << total(l + 1, r + 1) << "\n";
}
}
}
Java
import java.util.*;
import java.io.*;
public class Main {
static int n;
static long[] b1, b2; // two Fenwick trees, 1-indexed
static void add(long[] b, int i, long x) { for (; i <= n; i += i & -i) b[i] += x; }
static long sum(long[] b, int i) { long s = 0; for (; i > 0; i -= i & -i) s += b[i]; return s; }
static void rangeAdd(int l, int r, long x) {
add(b1, l, x); add(b1, r + 1, -x);
add(b2, l, x * (l - 1)); add(b2, r + 1, -x * r);
}
static long prefix(int i) { return sum(b1, i) * i - sum(b2, i); }
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedInputStream(System.in));
in.nextToken(); n = (int) in.nval; in.nextToken(); int q = (int) in.nval;
b1 = new long[n + 2]; b2 = new long[n + 2];
StringBuilder sb = new StringBuilder();
while (q-- > 0) {
in.nextToken(); int type = (int) in.nval;
if (type == 1) {
in.nextToken(); int l = (int) in.nval + 1; in.nextToken(); int r = (int) in.nval + 1; // gauges 0..n-1 -> 1..n
in.nextToken(); rangeAdd(l, r, (long) in.nval);
} else if (type == 2) {
in.nextToken(); int i = (int) in.nval + 1;
sb.append(sum(b1, i)).append('\n');
} else {
in.nextToken(); int l = (int) in.nval + 1; in.nextToken(); int r = (int) in.nval + 1;
sb.append(prefix(r) - prefix(l - 1)).append('\n');
}
}
System.out.print(sb);
}
}
5
27
3
11
Python
import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
b1, b2 = [0] * (n + 2), [0] * (n + 2) # two Fenwick trees, 1-indexed
def add(b, i, x):
while i <= n:
b[i] += x; i += i & -i
def total(b, i):
s = 0
while i > 0:
s += b[i]; i -= i & -i
return s
def prefix(i):
return total(b1, i) * i - total(b2, i)
out, p = [], 2
for _ in range(q):
t = int(data[p]); p += 1
if t == 1:
l, r, x = int(data[p]) + 1, int(data[p + 1]) + 1, int(data[p + 2]); p += 3 # 0-based -> 1-based
add(b1, l, x); add(b1, r + 1, -x)
add(b2, l, x * (l - 1)); add(b2, r + 1, -x * r)
elif t == 2:
i = int(data[p]) + 1; p += 1
out.append(total(b1, i))
else:
l, r = int(data[p]) + 1, int(data[p + 1]) + 1; p += 2
out.append(prefix(r) - prefix(l - 1))
print("\n".join(map(str, out)))
main()
5
27
3
11
Problem K2 · Pass the Parcel
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, k, t[500001]; // t: Fenwick tree of "still in the circle"
void add(int i, int x) { for (; i <= n; i += i & -i) t[i] += x; }
int kth(int k) { // the k-th child still in
int pos = 0;
for (int pw = 1 << 19; pw; pw >>= 1) // 2^19 > 5·10^5
if (pos + pw <= n && t[pos + pw] < k) { // whole block before the k-th?
pos += pw;
k -= t[pos];
}
return pos + 1;
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) add(i, 1);
int cur = 0;
for (int left = n; left > 0; left--) {
cur = (cur + k - 1) % left; // rank among those left
int who = kth(cur + 1);
add(who, -1);
cout << who << " ";
}
cout << "\n";
}
Java
import java.util.*;
public class Main {
static int n;
static int[] t; // Fenwick tree of "still in the circle"
static void add(int i, int x) { for (; i <= n; i += i & -i) t[i] += x; }
static int kth(int k) { // the k-th child still in
int pos = 0;
for (int pw = 1 << 19; pw > 0; pw >>= 1)
if (pos + pw <= n && t[pos + pw] < k) { pos += pw; k -= t[pos]; }
return pos + 1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt(); long k = sc.nextLong();
t = new int[n + 1];
for (int i = 1; i <= n; i++) add(i, 1);
StringBuilder sb = new StringBuilder();
int cur = 0;
for (int left = n; left > 0; left--) {
cur = (int) ((cur + k - 1) % left);
int who = kth(cur + 1);
add(who, -1);
sb.append(who).append(left > 1 ? " " : "\n");
}
System.out.print(sb);
}
}
3 6 2 7 5 1 4
Python
import sys
def main():
n, k = map(int, sys.stdin.read().split())
t = [0] * (n + 1) # Fenwick tree of "still in the circle"
def add(i, x):
while i <= n:
t[i] += x; i += i & -i
for i in range(1, n + 1):
add(i, 1)
top = 1 << max(0, n.bit_length() - 1) # the highest power of two <= n
def kth(k):
pos, pw = 0, top
while pw:
if pos + pw <= n and t[pos + pw] < k:
pos += pw; k -= t[pos]
pw >>= 1
return pos + 1
out, cur = [], 0
for left in range(n, 0, -1):
cur = (cur + k - 1) % left
who = kth(cur + 1)
add(who, -1)
out.append(who)
print(" ".join(map(str, out)))
main()
3 6 2 7 5 1 4