SyntaxPilot
Courses/Competitive Programming/Lesson 63
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 63 of 90

Fenwick tree tricks: range update, order statistics

queued

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 & −i is 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], then i −= i & −i (drop the lowest bit), until 0. prefix(7) = t[7] + t[6] + t[4].
  • Point add at i: add to t[i], then i += 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 = 0 and 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

  1. What does i & −i compute and why? The lowest set bit of i, because −i is the two's complement (~i + 1).
  2. What does t[i] store? The sum of the lowbit(i) values ending at i.
  3. 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.
  4. And range add + range sum? Two BITs: prefix(i) = sum1(i)·i − sum2(i) with marks x and x·(l − 1).
  5. 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.
  6. 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.
  7. 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