OA practice · 9 patterns · 72 problems

Segment Tree & BIT

Easy to hard inside each pattern. Rating: CF problems show the official rating, LC problems show the zerotrac contest rating (about CF level), and ~ marks my estimate (CSES, old LC).

0
Saved in this browser only

Which structure?

NeedUse
Static array, range sumprefix sums
Static, range min / gcd / AND, many queriessparse table (O(1) query)
Point update + prefix sum / count / k-thBIT
Range add + point query, or range add + range sumBIT on differences / two BITs
Point update + min / max / any merge, or "first index with ≥ x"segment tree (+ descend)
Range add / assign / flip + range querylazy segment tree
Sorted set with insert, erase, "how many < x"BIT over compressed values (or pbds)
Range queries with no updates, hard to mergeoffline: sort by right end / threshold

Spot it in an OA: q and n up to 1e5 with updates · "count smaller / greater before / after" · "k-th remaining" · "first position that fits" · subtree / path queries · dp[i] = best over earlier j with a value condition.

Templates (stress-tested against a brute force)
struct BIT {                                   // 1-based
    int n; vector<ll> t;
    BIT(int n) : n(n), t(n + 1) {}
    void add(int i, ll v) { for (; i <= n; i += i & -i) t[i] += v; }
    ll sum(int i) { ll s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; }
    int kth(ll k) {                            // smallest i with sum(i) >= k (counts >= 0)
        int pos = 0;
        for (int pw = 1 << __lg(n); pw; pw >>= 1)
            if (pos + pw <= n && t[pos + pw] < k) pos += pw, k -= t[pos];
        return pos + 1;
    }
};
struct RangeBIT {                              // range add, range sum (1-based)
    BIT b1, b2;
    RangeBIT(int n) : b1(n + 1), b2(n + 1) {}
    void add(int l, int r, ll v) { b1.add(l, v); b1.add(r + 1, -v); b2.add(l, v * (l - 1)); b2.add(r + 1, -v * r); }
    ll pre(int i) { return b1.sum(i) * i - b2.sum(i); }
    ll sum(int l, int r) { return pre(r) - pre(l - 1); }
};
struct SegTree {                               // iterative: point set, query [l, r), 0-based
    int n; vector<ll> t; ll ID = LLONG_MAX;    // ID = identity of merge
    ll merge(ll a, ll b) { return min(a, b); }
    SegTree(int n) : n(n), t(2 * n, LLONG_MAX) {}
    void set(int i, ll v) { for (t[i += n] = v; i > 1; i >>= 1) t[i >> 1] = merge(t[i & ~1], t[i | 1]); }
    ll query(int l, int r) {
        ll L = ID, R = ID;                     // keep the sides apart: merge may not commute
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) L = merge(L, t[l++]);
            if (r & 1) R = merge(t[--r], R);
        }
        return merge(L, R);
    }
};
struct LazySeg {                               // range add; {sum, min} on [l, r], 0-based
    int n; vector<ll> sm, mn, lz;
    LazySeg(int n) : n(n), sm(4 * n), mn(4 * n), lz(4 * n) {}
    void apply(int x, int len, ll v) { sm[x] += v * len; mn[x] += v; lz[x] += v; }
    void push(int x, int l, int r) {
        if (!lz[x]) return;
        int m = (l + r) / 2;
        apply(2 * x, m - l + 1, lz[x]); apply(2 * x + 1, r - m, lz[x]); lz[x] = 0;
    }
    void add(int ql, int qr, ll v, int x = 1, int l = 0, int r = -1) {
        if (r < 0) r = n - 1;
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) { apply(x, r - l + 1, v); return; }
        push(x, l, r); int m = (l + r) / 2;
        add(ql, qr, v, 2 * x, l, m); add(ql, qr, v, 2 * x + 1, m + 1, r);
        sm[x] = sm[2 * x] + sm[2 * x + 1]; mn[x] = min(mn[2 * x], mn[2 * x + 1]);
    }
    pair<ll, ll> query(int ql, int qr, int x = 1, int l = 0, int r = -1) {
        if (r < 0) r = n - 1;
        if (qr < l || r < ql) return {0, LLONG_MAX};
        if (ql <= l && r <= qr) return {sm[x], mn[x]};
        push(x, l, r); int m = (l + r) / 2;
        auto a = query(ql, qr, 2 * x, l, m), b = query(ql, qr, 2 * x + 1, m + 1, r);
        return {a.first + b.first, min(a.second, b.second)};
    }
};
vector<int> mx;                                // recursive max tree, size 4n, node x covers [l, r]
int firstAtLeast(int k, int x, int l, int r) { // descend: leftmost a[i] >= k, or -1
    if (mx[x] < k) return -1;
    if (l == r) return l;
    int m = (l + r) / 2, L = firstAtLeast(k, 2 * x, l, m);
    return L != -1 ? L : firstAtLeast(k, 2 * x + 1, m + 1, r);
}   // LC 3479 fruits [4,2,5], baskets [3,5,4] → 1 unplaced

A. BIT basics: updates, differences, k-th

  1. Dynamic Range Sum Queries
    CSES 1648
    ~1300
  2. Range Update Queries
    CSES 1651
    ~1400
  3. Queries on a Permutation With Key
    LC 1409
    1334
  4. Forest Queries II
    CSES 1739
    ~1600
  5. List Removals
    CSES 1749
    ~1700
  6. Multiset
    CF 1354D
    1900
  7. Messenger Simulator
    CF 1288E20-day #503
    2000
Ideas for this section
  • 1648: set = add(i, new − old). 1651: BIT on the difference array: add(l, v), add(r+1, −v), value = sum(i).
  • 1409 / 1288E: move-to-front: reserve m empty slots in front, each move clears the old slot and fills the next front slot; position = prefix count.
  • 1739: 2D BIT (nested loops), rectangle = 4 prefix sums.
  • 1749 / 1354D: BIT of 1s (or counts over values); kth(k) finds the element, then add(pos, −1). 1354D's memory limit rules out multiset.

B. Counting pairs / triplets (scan + BIT over values)

  1. Count Number of Teams
    LC 1395
    1343
  2. Maximum Crossings (Hard)
    CF 1676H2
    1500
  3. Greetings
    CF 1915F20-day #19
    1500
  4. Pashmak and Parmida's problem
    CF 459D
    1800
  5. Nested Segments
    CF 652D
    1800
  6. Petya and Array
    CF 1042D
    1800
  7. Reverse Pairs
    LC 493
    ~2000
  8. Number of Pairs Satisfying Inequality
    LC 242620-day #476
    2030
  9. Count of Range Sum
    LC 327
    ~2100
  10. Enemy is weak
    CF 61E20-day #190
    1900
  11. Create Sorted Array through Instructions
    LC 1649
    2207
  12. Count Good Triplets in an Array
    LC 2179
    2272
  13. Make Array Empty
    LC 2659
    2281
  14. Moving Points
    CF 1311Fsheet #48
    1900
Ideas for this section
  • 1395 / 61E / 2179: fix the middle: (smaller on the left) × (larger on the right), each from a BIT. 2179: first rewrite nums2 as positions in nums1, then count increasing triplets.
  • 1676H2: count pairs i < j with a[i] ≥ a[j] (≥, not >).
  • 459D: pre[i] = count of a[i] in a[1..i], suf[j] = count in a[j..n]; count i < j with pre[i] > suf[j] by scanning right to left with a BIT over suf values.
  • 652D: sort by right end; for each segment count earlier ones whose left is greater (compressed lefts).
  • 1042D / 327: prefix sums: P[r] − P[l] < t ⇔ P[l] > P[r] − t. Compress all P and all P − t, then count with a BIT while scanning r.
  • 493 / 2426: same scan, with the transformed value (2·a[j], c[j] + diff) also compressed.
  • 1649: cost = min(# less, # greater) seen so far.
  • 2659: visit in sorted value order; steps = count of remaining elements from the current position to the next (wrap around).

C. Offline: sort the queries

  1. Salary Queries
    CSES 1144
    ~1800
  2. Distinct Values Queries
    CSES 1734
    ~1900
  3. Little Elephant and Array
    CF 220Bsheet #64
    1800
  4. Mishka and Interesting sum
    CF 703D
    2100
  5. Find Building Where Alice and Bob Can Meet
    LC 2940
    2327
  6. Maximum Sum Queries
    LC 2736
    2533
Ideas for this section
  • 1144: read all queries first, compress every salary that ever appears, BIT over values.
  • 1734: sort queries by r; keep +1 only at the last occurrence of each value; answer = sum(l..r).
  • 703D: XOR of even-count values = (XOR of range) ^ (XOR of distinct values); distinct XOR uses the 1734 trick with a XOR-BIT.
  • 2940: answer = first index > max(a, b) with height > the taller one: max segment tree + descend (or offline with a monotonic stack).
  • 2736: sort points and queries by x descending, insert y into a max structure over compressed y, query the suffix ≥ yᵢ.

D. Segment tree: point update, range query, descend

  1. Dynamic Range Minimum Queries
    CSES 1649
    ~1300
  2. Iva & Pav
    CF 1878E
    1400
  3. Xenia and Bit Operations
    CF 339D
    1700
  4. Hotel Queries
    CSES 1143
    ~1700
  5. Peaks in Array
    LC 3187
    2154
  6. Fruits Into Baskets III
    LC 3479
    2178
  7. Ant colony
    CF 474F
    2100
  8. Serge and Dining Room
    CF 1179C
    2200
  9. Booking Concert Tickets in Groups
    LC 2286
    2470
Ideas for this section
  • 1878E: AND over [l, r] only falls as r grows → sparse table or segment tree + binary search on r.
  • 339D: the merge alternates OR / XOR by level.
  • 1143 / 3479: max tree; descend to the leftmost value ≥ x, then lower it.
  • 3187: store 1 at each peak; an update changes only i−1, i, i+1; query (l+1 .. r−1).
  • 474F: node = (gcd, min, count of min); the survivors are the elements equal to the gcd.
  • 1179C: on the value axis, a dish adds +1 to the prefix [1..a] and a pupil adds −1 to [1..b]; the answer is the rightmost x with value > 0 (lazy add + descend).
  • 2286: max tree for gather (first row with ≥ k free seats, within maxRow), sum tree + a first-not-full pointer for scatter.

E. Custom merge node

  1. Subarray Sum Queries
    CSES 1190
    ~1900
  2. SPOJ GSS1
    SPOJ GSS1InMobi OA
    ~1900
  3. Prefix Sum Queries
    CSES 2166
    ~1900
  4. Sereja and Brackets
    CF 380Csheet #49
    2000
  5. Palindrome Queries
    CSES 2420
    ~2000
  6. Editor
    CF 1263E
    2100
  7. Non-Decreasing Dilemma
    CF 1567Esheet #63
    2200
  8. Longest Substring of One Repeating Character
    LC 2213
    2628
  9. Maximum Sum of Subsequence With Non-adjacent Elements
    LC 3165
    2697
Ideas for this section
  • 1190 / GSS1: node (sum, best prefix, best suffix, best); best = max(a.best, b.best, a.suf + b.pre).
  • 2166: node (sum, max prefix); pre = max(a.pre, a.sum + b.pre).
  • 2420: forward and reverse polynomial hashes in two trees; a palindrome has equal hashes.
  • 1263E: brackets as ±1, node (sum, min prefix, max prefix); valid ⇔ sum = 0 and min ≥ 0; depth = max prefix.
  • 2213 / 1567E: node (prefix run, suffix run, best / count) + the end characters; join runs across the middle.
  • 3165: node = 2×2 table best[first taken?][last taken?]; merge forbids taken|taken across the cut.

F. Lazy propagation

  1. My Calendar III
    LC 732
    ~1900
  2. Falling Squares
    LC 699
    ~1900
  3. XOR on Segment
    CF 242Esheet #62
    2000
  4. Range Module
    LC 715
    ~2100
  5. Range Updates and Sums
    CSES 1735
    ~2100
  6. Polynomial Queries
    CSES 1736
    ~2100
  7. Circular RMQ
    CF 52C
    2200
  8. Rectangle Area II
    LC 850
    2235
  9. Handling Sum Queries After Update
    LC 2569
    2397
  10. Subarrays Distinct Element Sum of Squares II
    LC 2916
    2816
Ideas for this section
  • 732: range add + global max over compressed (or dynamic) coordinates.
  • 699: range assign (new height) + range max on compressed x.
  • 715: range assign 0/1 + "is the whole range 1" (min = 1), dynamic nodes.
  • 2569 / 242E: lazy flip; ones = len − ones. 242E keeps 20 per-bit trees.
  • 1735: two tags; assign wipes the pending add, add on top of assign just adds.
  • 1736: add 1, 2, 3… = an arithmetic progression; tag (first, step), and two APs add up to one AP.
  • 52C: a wrapped range = two normal ranges.
  • 850: sweep x; the tree over compressed y keeps (cover count, covered length), no push needed.
  • 2916: move the right end r; x adds +1 to the counts of left ends in (last[x], r]; Σ(c+1)² = Σc² + 2Σc + len, so keep the sum under range add.

G. DP sped up with a tree over values

  1. Number of Longest Increasing Subsequence
    LC 673
    ~1800
  2. Subsequences
    CF 597C
    1900
  3. Best Team With No Conflicts
    LC 1626
    2027
  4. Optimal Partition
    CF 1667B
    2100
  5. Longest Increasing Subsequence II
    LC 2407
    2280
Ideas for this section
  • 673: BIT over values storing (best length, count); merge equal lengths by adding counts.
  • 597C: k+1 BITs; dp[j][v] = Σ dp[j−1][values < v].
  • 1626: sort by (age, score); dp = score + prefix max of dp over scores ≤: a max-BIT.
  • 2407: dp[v] = 1 + max dp[v−k .. v−1]: a max segment tree indexed by value.
  • 1667B: dp[i] = max dp[j] + sign(P[i] − P[j])·(i − j); three cases by sign → three max trees over compressed P storing dp[j] − j, dp[j], dp[j] + j.

H. Trees: Euler tour + BIT / segment tree

  1. Subtree Queries
    CSES 1137
    ~1700
  2. Path Queries
    CSES 1138
    ~1800
  3. Propagating tree
    CF 383C20-day #427
    2000
  4. Danil and a Part-time Job
    CF 877E20-day #401
    2000
  5. A Growing Tree
    CF 1891F20-day #472
    2000
  6. Water Tree
    CF 343D
    2100
  7. New Year Tree
    CF 620Esheet #108
    2100
  8. Path Queries II
    CSES 2134sheet #110, HLD
    ~2300
Ideas for this section
  • 1137: subtree = [tin, tout]; point update, range sum.
  • 1138: root-to-v sum: changing v's value is a range add on v's subtree; the answer is a point query.
  • 343D: fill v = assign the time on v's subtree range; empty v = set the time at tin[v] (a point). v is full ⇔ last fill of v > max empty time inside v's subtree.

I. Stretch (rare in OAs)

  1. Army Creation
    CF 813E
    2200
  2. The Child and Sequence
    CF 438D
    2300
  3. Multidimensional Queries
    CF 1093G
    2300
  4. Block Placement Queries
    LC 3161
    2513
Ideas for this section
  • 813E: count i in [l, r] whose k-th previous equal value is < l: persistent tree or merge-sort tree (online).
  • 438D: range mod: recurse only where max ≥ x; each mod at least halves the value, so the total work is small.
  • 1093G: for each of the 2^(k−1) sign masks keep a max and min tree of the ± sum; answer = max over masks of (max − min).
  • 3161: ordered set of obstacles + a max tree of "gap ending at x"; a query = max on [0, prev obstacle] and the last gap.

Past OA questions → row

OA questionPattern
InMobi: max subarray sum in [x, y], many queriesE · GSS1
Pokémon leaderboard (Euler tour + Fenwick)H · 1137
Product display move-to-front (arrays Q50)A · 1409, 1288E
Squarepoint log analysis (k adjacent swaps)fenwick · LC 1505
WF tricky subarraysprefix min/max + binary search (D · 1878E style)
Range frequency-XORMo's, not a tree (C · 703D is the tree version)
Trim zeroesset<int> of 1-positions, no tree needed

Traps

QuestionAnswer
BIT index 0?Infinite loop: shift to 1-based
Recursive tree size?4n
Lazy: when to push?Before going into the children, in both update and query
Iterative query with a non-commutative merge?Keep left and right results separate (see the template)
Values up to 1e9?Compress, including every value the queries use
Sum range?sum(r) − sum(l − 1); long long for sums and counts of pairs
Two lazy tags (assign + add)?Assign clears the pending add; write compose once and test it
Max with a BIT?Only when values only increase (prefix max); otherwise use a segment tree