9. Range queries · DSA Mastery

A range query asks for a value computed from a subarray [a, b] of an array. The three classics are:

sumq(a, b) — the sum of the values in [a, b]
minq(a, b) — the minimum value in [a, b]
maxq(a, b) — the maximum value in [a, b]

For the array [1, 3, 8, 4, 6, 1, 3, 4] and the range [3, 6] (values 4, 6, 1, 3): sumq(3, 6) = 14, minq(3, 6) = 1 and maxq(3, 6) = 6.

The obvious approach loops over the range. That costs O(n) per query, so q queries cost O(nq). With n = q = 2·10⁵ that is 4·10¹⁰ steps, far too slow. This chapter is about doing better: first for arrays that never change, then for arrays that get updated between queries.

Range query ka matlab hai: array ke kisi subarray [a, b] pe koi value nikaalna. Teen classic queries hain:

sumq(a, b) — [a, b] ki saari values ka sum
minq(a, b) — [a, b] mein sabse chhoti value
maxq(a, b) — [a, b] mein sabse badi value

Array [1, 3, 8, 4, 6, 1, 3, 4] aur range [3, 6] lo (values 4, 6, 1, 3): sumq(3, 6) = 14, minq(3, 6) = 1 aur maxq(3, 6) = 6.

Seedha tareeka hai range pe loop chalana. Har query O(n), toh q queries O(nq). Agar n = q = 2·10⁵ ho, toh 4·10¹⁰ steps — time limit mein bilkul nahi chalega. Is chapter mein hum isse kaafi better karna seekhenge: pehle aise arrays ke liye jo kabhi badalte nahi, phir aise arrays ke liye jinme queries ke beech updates aate hain.

9.1Static array queries

When the array is static (never updated between queries), we can spend some time up front building a structure that answers any query quickly.

Jab array static ho (queries ke beech kabhi update nahi hota), tab hum shuru mein thoda time lagakar ek structure bana sakte hain jo phir har query ka jawab jaldi de de.

Sum queries: prefix sums

Build a prefix sum array p where p[k] is the sum of arr[0..k], i.e. p[k] = sumq(0, k). Each entry is the previous one plus one new element, so the whole array takes O(n) to build.

For arr = [1, 3, 4, 8, 6, 1, 4, 2] we get p = [1, 4, 8, 16, 22, 23, 27, 29].

Now any range sum is the difference of two prefix sums:

Ek prefix sum array p banao jisme p[k] = arr[0..k] ka sum, yaani p[k] = sumq(0, k). Har entry = pichhli entry + ek naya element. Toh poora array O(n) mein ban jaata hai.

arr = [1, 3, 4, 8, 6, 1, 4, 2] ke liye p = [1, 4, 8, 16, 22, 23, 27, 29] milta hai.

Ab koi bhi range sum, do prefix sums ka difference hai. Socho: 0 se b tak ka total lo, aur usme se 0 se a−1 tak ka total hata do — beech wala hissa bach jayega:

\text{sumq}(a, b) = \text{sumq}(0, b) - \text{sumq}(0, a - 1)

We define sumq(0, −1) = 0, so the formula also works when a = 0. Example: sumq(3, 6) = p[6] − p[2] = 27 − 8 = 19, which matches 8 + 6 + 1 + 4.

sumq(0, −1) = 0 maan lete hain, taaki a = 0 pe bhi formula chal jaye. Example: sumq(3, 6) = p[6] − p[2] = 27 − 8 = 19 — check karo, 8 + 6 + 1 + 4 = 19. Ekdum sahi!

JAVAch09/PrefixSums.java

1/** p[k] = arr[0] + arr[1] + ... + arr[k] */2static long[] build(int[] arr) {3    long[] p = new long[arr.length];4    for (int k = 0; k < arr.length; k++) {5        p[k] = (k > 0 ? p[k - 1] : 0) + arr[k];6    }7    return p;8}

/** p[k] = arr[0] + arr[1] + ... + arr[k] */
static long[] build(int[] arr) {
    long[] p = new long[arr.length];
    for (int k = 0; k < arr.length; k++) {
        p[k] = (k > 0 ? p[k - 1] : 0) + arr[k];
    }
    return p;
}

JAVAch09/PrefixSums.java

1/** sumq(a, b) in O(1). sumq(0, -1) counts as 0, so a = 0 needs no special case. */2static long sumq(long[] p, int a, int b) {3    return p[b] - (a > 0 ? p[a - 1] : 0);4}

/** sumq(a, b) in O(1). sumq(0, -1) counts as 0, so a = 0 needs no special case. */
static long sumq(long[] p, int a, int b) {
    return p[b] - (a > 0 ? p[a - 1] : 0);
}

VisualiserPrefix sum array

Show

Array

query range
added (+)
subtracted (−)
used in answer

arr

0123456713486142sumq(3,6)

p (prefix sums)

012345671481622232729

1/4

Query sumq(3, 6). A loop would touch 4 elements; with the prefix array we need only two lookups.

1/** sumq(a, b) in O(1). sumq(0, -1) counts as 0, so a = 0 needs no special case. */2static long sumq(long[] p, int a, int b) {3    return p[b] - (a > 0 ? p[a - 1] : 0);4}

a: 3
b: 6

Java noteJava note

Use long[] for prefix sums. With n = 2·10⁵ values up to 10⁹, a prefix sum can reach 2·10¹⁴, far above Integer.MAX_VALUE (≈ 2.1·10⁹). Java will not warn you: the int silently wraps around to a wrong (often negative) value.

A common alternative is an array of size n + 1 with p[0] = 0 and p[k + 1] = p[k] + arr[k]. Then sumq(a, b) = p[b + 1] − p[a], with no a > 0 check.

Prefix sums ke liye long[] lo. n = 2·10⁵ aur values 10⁹ tak hon, toh prefix sum 2·10¹⁴ tak ja sakta hai — Integer.MAX_VALUE (≈ 2.1·10⁹) se bahut zyada. Java koi warning nahi deta: int chupchaap overflow hokar galat (aksar negative) value de deta hai.

Ek aur popular tareeka: n + 1 size ka array, p[0] = 0 aur p[k + 1] = p[k] + arr[k]. Phir sumq(a, b) = p[b + 1] − p[a] — a > 0 wala check hi nahi chahiye.

Two-dimensional prefix sums

The same idea works in 2D. Let s[i][j] be the sum of the rectangle from the top-left corner to (i, j). Then the sum of any rectangle is

S(A) − S(B) − S(C) + S(D)

where A is the rectangle’s bottom-right corner, B the cell just above its top-right corner, C the cell just left of its bottom-left corner, and D the cell diagonally up-left of its top-left corner. Each S(X) is the prefix rectangle ending at X. B and C both contain D’s area, so D gets subtracted twice and has to be added back once. That is inclusion–exclusion.

Building s uses the same trick in reverse: s[i][j] = cell + s[i−1][j] + s[i][j−1] − s[i−1][j−1].

Yahi idea 2D mein bhi chalta hai. s[i][j] = top-left corner se (i, j) tak ke rectangle ka sum. Phir kisi bhi rectangle ka sum hai:

S(A) − S(B) − S(C) + S(D)

A humare rectangle ka bottom-right corner hai, B uske top-right ke theek upar wala cell, C bottom-left ke theek left wala cell, aur D top-left ke diagonal upar-left wala cell. Har S(X) corner se X tak ka prefix rectangle hai. Dhyaan do: B aur C dono mein D ka area aata hai — toh D do baar minus ho gaya. Isliye ek baar wapas jodna padta hai. Isi ko inclusion–exclusion kehte hain.

s banane mein bhi yahi trick ulti chalti hai: s[i][j] = cell + s[i−1][j] + s[i][j−1] − s[i−1][j−1].

JAVAch09/PrefixSums.java

1/** s[i][j] = sum of the rectangle (1,1)..(i,j). Row 0 and column 0 stay 0, so there are no edge cases. */2static long[][] build2D(int[][] g) {3    int rows = g.length, cols = g[0].length;4    long[][] s = new long[rows + 1][cols + 1];5    for (int i = 1; i <= rows; i++) {6        for (int j = 1; j <= cols; j++) {7            s[i][j] = g[i - 1][j - 1] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];8        }9    }10    return s;11}

/** s[i][j] = sum of the rectangle (1,1)..(i,j). Row 0 and column 0 stay 0, so there are no edge cases. */
static long[][] build2D(int[][] g) {
    int rows = g.length, cols = g[0].length;
    long[][] s = new long[rows + 1][cols + 1];
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            s[i][j] = g[i - 1][j - 1] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    return s;
}

JAVAch09/PrefixSums.java

1/** Sum of rows r1..r2 and columns c1..c2 (1-indexed, inclusive) = S(A) - S(B) - S(C) + S(D). */2static long rect(long[][] s, int r1, int c1, int r2, int c2) {3    return s[r2][c2] - s[r1 - 1][c2] - s[r2][c1 - 1] + s[r1 - 1][c1 - 1];4}

/** Sum of rows r1..r2 and columns c1..c2 (1-indexed, inclusive) = S(A) - S(B) - S(C) + S(D). */
static long rect(long[][] s, int r1, int c1, int r2, int c2) {
    return s[r2][c2] - s[r1 - 1][c2] - s[r2][c1 - 1] + s[r1 - 1][c1 - 1];
}

Visualiser2D prefix sums — S(A) − S(B) − S(C) + S(D)

Show

added (+)
subtracted (−)
used in answer

grid g (1-indexed)

12345123431415926535897932384?

s (prefix sums, with zero border)

s012345012340000000348914012152531390172847607702033557697

1/6

We want the sum of rows 2..4, columns 2..4. Formula: S(A) − S(B) − S(C) + S(D).

1/** Sum of rows r1..r2 and columns c1..c2 (1-indexed, inclusive) = S(A) - S(B) - S(C) + S(D). */2static long rect(long[][] s, int r1, int c1, int r2, int c2) {3    return s[r2][c2] - s[r1 - 1][c2] - s[r2][c1 - 1] + s[r1 - 1][c1 - 1];4}

r1: 2
c1: 2
r2: 4
c2: 4

Minimum queries: the sparse table

Minimum queries are harder: you can’t “subtract” a minimum the way you subtract a sum. Still, after O(n log n) preprocessing we can answer any minq(a, b) in O(1). (Max works the same way.)

The idea is to precompute minq for every range whose length is a power of two: lengths 1, 2, 4, 8, …. There are O(log n) such lengths and n starting points, so O(n log n) values in total. Each one comes from two halves of half the length:

Minimum queries thodi mushkil hain: sum ki tarah minimum ko “subtract” nahi kar sakte. Phir bhi O(n log n) preprocessing ke baad koi bhi minq(a, b) O(1) mein mil sakta hai. (Max bhi bilkul aise hi.)

Idea: har us range ka minq pehle se nikaal lo jiski length power of two ho — 1, 2, 4, 8, …. Aisi O(log n) lengths hain aur n starting points, toh total O(n log n) values. Har value apne do halves (aadhi length wale) se ban jaati hai:

\text{minq}(a, b) = \min\big(\text{minq}(a,\ a + w - 1),\ \text{minq}(a + w,\ b)\big), \quad w = \tfrac{b - a + 1}{2}

Query. Let k be the largest power of two with k ≤ b − a + 1. Two blocks of length k, one starting at a and one ending at b, together cover [a, b]. They may overlap, and for minimum that’s fine:

minq(a, b) = min(minq(a, a + k − 1), minq(b − k + 1, b))

Example on [1, 3, 4, 8, 6, 1, 4, 2]: the range [1, 6] has length 6, so k = 4, and [1, 6] = [1, 4] ∪ [3, 6]. Since minq(1, 4) = 3 and minq(3, 6) = 1, the answer is 1.

Query. k = sabse bada power of two jo b − a + 1 se chhota ya barabar ho. Length k ke do blocks — ek a se shuru, ek b pe khatam — milkar poora [a, b] cover kar lete hain. Beech mein overlap ho sakta hai, aur minimum ke liye isse koi farak nahi padta:

minq(a, b) = min(minq(a, a + k − 1), minq(b − k + 1, b))

Example [1, 3, 4, 8, 6, 1, 4, 2] pe: range [1, 6] ki length 6 hai, toh k = 4, aur [1, 6] = [1, 4] ∪ [3, 6]. minq(1, 4) = 3 aur minq(3, 6) = 1, toh answer 1.

JAVAch09/SparseTable.java

1final int[][] mn; // mn[j][i] = min of arr[i .. i + 2^j - 1]2 3SparseTable(int[] arr) {4    int n = arr.length;5    int levels = 32 - Integer.numberOfLeadingZeros(n); // lengths 1, 2, 4, ... up to n6    mn = new int[levels][];7    mn[0] = arr.clone();8    for (int j = 1; j < levels; j++) {9        int w = 1 << (j - 1); // half of the block length 2^j10        mn[j] = new int[n - (1 << j) + 1];11        for (int i = 0; i < mn[j].length; i++) {12            mn[j][i] = Math.min(mn[j - 1][i], mn[j - 1][i + w]);13        }14    }15}

final int[][] mn; // mn[j][i] = min of arr[i .. i + 2^j - 1]

SparseTable(int[] arr) {
    int n = arr.length;
    int levels = 32 - Integer.numberOfLeadingZeros(n); // lengths 1, 2, 4, ... up to n
    mn = new int[levels][];
    mn[0] = arr.clone();
    for (int j = 1; j < levels; j++) {
        int w = 1 << (j - 1); // half of the block length 2^j
        mn[j] = new int[n - (1 << j) + 1];
        for (int i = 0; i < mn[j].length; i++) {
            mn[j][i] = Math.min(mn[j - 1][i], mn[j - 1][i + w]);
        }
    }
}

JAVAch09/SparseTable.java

1/** minq(a, b): two blocks of length 2^j (possibly overlapping) cover [a, b] exactly. */2int min(int a, int b) {3    int j = 31 - Integer.numberOfLeadingZeros(b - a + 1);4    return Math.min(mn[j][a], mn[j][b - (1 << j) + 1]);5}

/** minq(a, b): two blocks of length 2^j (possibly overlapping) cover [a, b] exactly. */
int min(int a, int b) {
    int j = 31 - Integer.numberOfLeadingZeros(b - a + 1);
    return Math.min(mn[j][a], mn[j][b - (1 << j) + 1]);
}

VisualiserSparse table for minimum queries

Show

Array

query range
being read
used in answer

arr

0123456713486142minq(1,6)

mn[j][i] = min of arr[i .. i + 2^j − 1]

len012345672^02^12^22^3134861421346112131111

1/4

Query minq(1, 6). The range has length 6.

1/** minq(a, b): two blocks of length 2^j (possibly overlapping) cover [a, b] exactly. */2int min(int a, int b) {3    int j = 31 - Integer.numberOfLeadingZeros(b - a + 1);4    return Math.min(mn[j][a], mn[j][b - (1 << j) + 1]);5}

a: 1
b: 6
length: 6

Static queries
Prefix sums: build	O(n)	one pass
Prefix sums: sumq(a, b)	O(1)	two lookups
2D prefix sums: build / query	O(R·C) / O(1)	four lookups
Sparse table: build	O(n log n)	log n rows
Sparse table: minq(a, b)	O(1)	two overlapping blocks

My notesMere notes

I understand 9.1 — mark as done9.1 samajh aa gaya — done mark karo

9.2Binary indexed tree

A prefix sum array breaks as soon as you update a value: every prefix after it changes, so you’d rebuild in O(n). A binary indexed tree, also called a Fenwick tree, is a dynamic version of prefix sums. Both of its operations are O(log n):

sum(k): compute sumq(1, k)
add(k, x): increase the value at position k by x

Fenwick trees are 1-indexed, which makes the bit tricks below work out cleanly.

Prefix sum array tab tak hi kaam ka hai jab tak koi value update na ho. Ek value badli, toh uske baad ka har prefix badal jaata hai — O(n) mein dobara banana padega. Binary indexed tree (jise Fenwick tree bhi kehte hain) prefix sums ka dynamic version hai. Iske dono operations O(log n) mein:

sum(k): sumq(1, k) nikaalo
add(k, x): position k ki value mein x jodo

Fenwick tree 1-indexed hota hai — isi se neeche wali bit tricks saaf-suthri chalti hain.

Structure

Let p(k) be the largest power of two that divides k. The tree is just an array where

tree[k] = sumq(k − p(k) + 1, k)

so each position stores the sum of the p(k) elements ending at k. For example p(6) = 2, so tree[6] = sumq(5, 6); and p(8) = 8, so tree[8] holds the sum of the first eight elements.

For arr = [1, 3, 4, 8, 6, 1, 4, 2] (positions 1–8) the tree is [1, 4, 4, 16, 6, 7, 4, 29]. The bars in the visualiser below draw these ranges.

Query. Any prefix [1, k] splits into O(log n) stored ranges. For example, sumq(1, 7) = sumq(1, 4) + sumq(5, 6) + sumq(7, 7) = 16 + 7 + 4 = 27. For a general range use the prefix-sum trick: sumq(a, b) = sumq(1, b) − sumq(1, a − 1).

Update. Changing position 3 affects every stored range containing it: tree[3], tree[4] and tree[8]. Each position belongs to O(log n) ranges.

p(k) = sabse bada power of two jo k ko divide karta hai. Tree bas ek array hai jisme

tree[k] = sumq(k − p(k) + 1, k)

yaani har position pe un p(k) elements ka sum hai jo k pe khatam hote hain. Jaise p(6) = 2, toh tree[6] = sumq(5, 6); aur p(8) = 8, toh tree[8] mein pehle aath elements ka sum hai.

arr = [1, 3, 4, 8, 6, 1, 4, 2] (positions 1–8) ke liye tree hai [1, 4, 4, 16, 6, 7, 4, 29]. Neeche visualiser mein bars inhi ranges ko dikhate hain — ek baar dhyaan se dekho.

Query. Koi bhi prefix [1, k] O(log n) stored ranges mein toot jaata hai. Jaise sumq(1, 7) = sumq(1, 4) + sumq(5, 6) + sumq(7, 7) = 16 + 7 + 4 = 27. General range ke liye wahi prefix-sum trick: sumq(a, b) = sumq(1, b) − sumq(1, a − 1).

Update. Position 3 badli, toh har woh stored range badlegi jisme 3 aata hai: tree[3], tree[4] aur tree[8]. Har position sirf O(log n) ranges mein hoti hai.

Implementation: `k & -k`

The key fact is that p(k) = k & -k. In two’s complement, -k is ~k + 1: every bit flips, and the +1 carries up to the lowest 1-bit of k. So k and -k share only that lowest 1-bit, and & isolates it. For k = 12 = 1100₂, k & -k = 0100₂ = 4.

sum walks down: k -= k & -k clears the lowest 1-bit, which jumps to the end of the next range to the left.
add walks up: k += k & -k moves to the next range that also contains position k.

Each step removes a 1-bit (sum) or pushes the lowest 1-bit higher (add). A number has at most ⌊log₂ n⌋ + 1 bits, so both loops are O(log n).

Asli trick: p(k) = k & -k. Two’s complement mein -k = ~k + 1 — saare bits ulat jaate hain, aur +1 ka carry k ke sabse neeche wale 1-bit tak pahunch jaata hai. Isliye k aur -k mein sirf wahi lowest 1-bit common hota hai, aur & use alag kar deta hai. k = 12 = 1100₂ ke liye k & -k = 0100₂ = 4.

sum neeche chalta hai: k -= k & -k lowest 1-bit hata deta hai — yaani left wali agli range ke end pe jump.
add upar chalta hai: k += k & -k us agli range pe le jaata hai jisme position k bhi aati hai.

Har step ya toh ek 1-bit hatata hai (sum) ya lowest 1-bit ko upar dhakelta hai (add). Kisi number mein max ⌊log₂ n⌋ + 1 bits hote hain, isliye dono loops O(log n).

JAVAch09/FenwickTree.java

1final int n;2final long[] tree; // tree[k] = sum of arr[k - p(k) + 1 .. k], where p(k) = k & -k3 4FenwickTree(int n) {5    this.n = n;6    tree = new long[n + 1];7}8 9/** sumq(1, k) */10long sum(int k) {11    long s = 0;12    while (k >= 1) {13        s += tree[k];14        k -= k & -k;15    }16    return s;17}18 19/** arr[k] += x  (x may be negative) */20void add(int k, long x) {21    while (k <= n) {22        tree[k] += x;23        k += k & -k;24    }25}26 27/** sumq(a, b) = sumq(1, b) - sumq(1, a - 1) */28long sum(int a, int b) {29    return sum(b) - sum(a - 1);30}

final int n;
final long[] tree; // tree[k] = sum of arr[k - p(k) + 1 .. k], where p(k) = k & -k

FenwickTree(int n) {
    this.n = n;
    tree = new long[n + 1];
}

/** sumq(1, k) */
long sum(int k) {
    long s = 0;
    while (k >= 1) {
        s += tree[k];
        k -= k & -k;
    }
    return s;
}

/** arr[k] += x  (x may be negative) */
void add(int k, long x) {
    while (k <= n) {
        tree[k] += x;
        k += k & -k;
    }
}

/** sumq(a, b) = sumq(1, b) - sumq(1, a - 1) */
long sum(int a, int b) {
    return sum(b) - sum(a - 1);
}

VisualiserBinary indexed tree (Fenwick tree)

Operation

Array (1-indexed)

current
used in answer
query range

arr

1234567813486142sumq(1,7)

tree

123456781441667429

1/11

Prefix query sumq(1, 7). We jump downwards from k, peeling off one stored range at a time.

1/** sumq(1, k) */2long sum(int k) {3    long s = 0;4    while (k >= 1) {5        s += tree[k];6        k -= k & -k;7    }8    return s;9}

k: 7
s: 0

JAVAch09/FenwickTree.java

1/** O(n) construction from a 0-indexed array: each range passes its total up to the next range. */2static FenwickTree of(int[] a) {3    FenwickTree f = new FenwickTree(a.length);4    for (int k = 1; k <= f.n; k++) {5        f.tree[k] += a[k - 1];6        int next = k + (k & -k);7        if (next <= f.n) f.tree[next] += f.tree[k];8    }9    return f;10}

/** O(n) construction from a 0-indexed array: each range passes its total up to the next range. */
static FenwickTree of(int[] a) {
    FenwickTree f = new FenwickTree(a.length);
    for (int k = 1; k <= f.n; k++) {
        f.tree[k] += a[k - 1];
        int next = k + (k & -k);
        if (next <= f.n) f.tree[next] += f.tree[k];
    }
    return f;
}

My notesMere notes

I understand 9.2 — mark as done9.2 samajh aa gaya — done mark karo

9.3Segment tree

A segment tree also supports range queries and value updates in O(log n), but it is more general than a Fenwick tree. A Fenwick tree needs an operation you can undo (sum: subtract the prefix), while a segment tree handles minimum, maximum, gcd, xor and much more. The price is about twice the memory and slightly more code.

Segment tree bhi range query aur value update dono O(log n) mein karta hai, par yeh Fenwick tree se zyada general hai. Fenwick ko aisa operation chahiye jise undo kar sako (sum mein prefix ghata do), jabki segment tree minimum, maximum, gcd, xor aur bahut kuch sambhal leta hai. Keemat: lagbhag double memory aur thoda zyada code.

Structure

A segment tree is a binary tree whose leaves are the array elements. Every internal node stores the answer (here: the sum) for the range of leaves below it. Assume n is a power of two and indices are 0-based. For [5, 8, 6, 3, 2, 7, 2, 6] the levels are 39, then 22 17, then 13 9 9 8, then the array itself.

Query. Any range splits into O(log n) nodes. Taking nodes as high as possible, you never need more than two per level. For [2, 7], sumq(2, 7) = 26 comes from just two nodes: 9 (covering [2, 3]) + 17 (covering [4, 7]).

Update. Changing one value only affects the nodes on the path from that leaf to the root. That’s O(log n) nodes.

Segment tree ek binary tree hai jiske leaves array ke elements hain. Har internal node apne neeche wale leaves ki range ka answer (yahan: sum) store karta hai. Maan lo n power of two hai aur indexing 0-based. [5, 8, 6, 3, 2, 7, 2, 6] ke liye levels hain: 39, phir 22 17, phir 13 9 9 8, phir khud array.

Query. Koi bhi range O(log n) nodes mein toot jaati hai. Agar nodes jitna ho sake upar se lo, toh kisi bhi level pe do se zyada nodes nahi lagte. [2, 7] ke liye sumq(2, 7) = 26 sirf do nodes se aata hai: 9 ([2, 3] cover karta hai) + 17 ([4, 7] cover karta hai).

Update. Ek value badli, toh sirf us leaf se root tak ke path wale nodes badalte hain — O(log n) nodes.

Implementation: a tree inside an array

Store the tree in one array of size 2n, top to bottom like a heap. tree[1] is the root, the children of tree[k] are tree[2k] and tree[2k + 1], and its parent is tree[k / 2]. The leaves (the original array) sit at tree[n] … tree[2n − 1]. So left children have even indices and right children have odd indices, and the query loop relies on exactly that.

The query keeps a range [a, b] of node indices, starting at the leaves [a + n, b + n], and climbs one level per iteration:

If a is odd, it’s a right child. Its parent would also cover something to the left of our range, so add tree[a] on its own and step a right.
If b is even, it’s a left child. Its parent would spill past the right end, so add tree[b] on its own and step b left.
Then a /= 2; b /= 2 moves up a level. Stop when a > b.

Poore tree ko 2n size ke ek array mein rakho, upar se neeche, heap ki tarah. tree[1] root hai, tree[k] ke children tree[2k] aur tree[2k + 1], aur parent tree[k / 2]. Leaves (original array) tree[n] … tree[2n − 1] pe baithte hain. Matlab left children ke index even, right children ke odd — query loop isi baat pe tika hai.

Query node indices ki ek range [a, b] rakhti hai — leaves [a + n, b + n] se shuru — aur har iteration mein ek level upar chadhti hai:

Agar a odd hai, toh woh right child hai. Uska parent humari range ke left ka hissa bhi le lega — isliye tree[a] ko akele jodo aur a ko ek right khiskao.
Agar b even hai, toh woh left child hai. Uska parent right end se bahar chala jayega — isliye tree[b] akele jodo aur b ko ek left khiskao.
Phir a /= 2; b /= 2 — ek level upar. Jab a > b ho jaye, ruk jao.

JAVAch09/SegmentTree.java

1final int n; // number of leaves (pad the array with zeros up to a power of two)2final long[] tree; // tree[1] = root, children of k are 2k and 2k+1, leaves are tree[n .. 2n-1]3 4SegmentTree(int[] arr) {5    n = arr.length;6    tree = new long[2 * n];7    for (int i = 0; i < n; i++) tree[n + i] = arr[i];8    for (int k = n - 1; k >= 1; k--) {9        tree[k] = tree[2 * k] + tree[2 * k + 1];10    }11}12 13/** sumq(a, b), 0-indexed and inclusive. */14long sum(int a, int b) {15    a += n; b += n;16    long s = 0;17    while (a <= b) {18        if (a % 2 == 1) s += tree[a++];19        if (b % 2 == 0) s += tree[b--];20        a /= 2; b /= 2;21    }22    return s;23}24 25/** arr[k] += x, then fix every ancestor of the leaf. */26void add(int k, long x) {27    k += n;28    tree[k] += x;29    for (k /= 2; k >= 1; k /= 2) {30        tree[k] = tree[2 * k] + tree[2 * k + 1];31    }32}

final int n; // number of leaves (pad the array with zeros up to a power of two)
final long[] tree; // tree[1] = root, children of k are 2k and 2k+1, leaves are tree[n .. 2n-1]

SegmentTree(int[] arr) {
    n = arr.length;
    tree = new long[2 * n];
    for (int i = 0; i < n; i++) tree[n + i] = arr[i];
    for (int k = n - 1; k >= 1; k--) {
        tree[k] = tree[2 * k] + tree[2 * k + 1];
    }
}

/** sumq(a, b), 0-indexed and inclusive. */
long sum(int a, int b) {
    a += n; b += n;
    long s = 0;
    while (a <= b) {
        if (a % 2 == 1) s += tree[a++];
        if (b % 2 == 0) s += tree[b--];
        a /= 2; b /= 2;
    }
    return s;
}

/** arr[k] += x, then fix every ancestor of the leaf. */
void add(int k, long x) {
    k += n;
    tree[k] += x;
    for (k /= 2; k >= 1; k /= 2) {
        tree[k] = tree[2 * k] + tree[2 * k + 1];
    }
}

VisualiserSegment tree (bottom-up)

Tree stores

Operation

Array (length 1, 2, 4, 8 or 16)

query range
current
being read
used in answer

stored as one array: tree[1 .. 2n−1]

1234567891011121314153922171399858632726

1/10

sumq(2, 7): start at the leaves. a = 2 + 8 = 10, b = 7 + 8 = 15.

1/** sumq(a, b), 0-indexed and inclusive. */2long sum(int a, int b) {3    a += n; b += n;4    long s = 0;5    while (a <= b) {6        if (a % 2 == 1) s += tree[a++];7        if (b % 2 == 0) s += tree[b--];8        a /= 2; b /= 2;9    }10    return s;11}

a: 10
b: 15
s: 0

Other queries

A segment tree works for any query where you can split a range into two parts, answer each part, and combine the answers: minimum, maximum, gcd, and bitwise and/or/xor. Only the combine function and its identity value change. In the min tree below, every node holds the smallest value in its range, and the root holds the minimum of the whole array.

Switch the visualiser above to min to try it. In the min tree the structure also allows a binary search: to find where the minimum is, walk down from the root, always into a child holding the same value. That takes O(log n).

Segment tree har us query pe chalta hai jahan range ko do hisson mein tod sako, dono ka answer nikaal sako, aur un answers ko combine kar sako: minimum, maximum, gcd, bitwise and/or/xor. Badalta sirf combine function aur uski identity value hai. Neeche wale min tree mein har node apni range ki sabse chhoti value rakhta hai, aur root poore array ka minimum.

Upar wale visualiser ko min pe switch karke khud try karo. Min tree mein binary search bhi ho jaata hai: minimum kahan hai, yeh dhundhne ke liye root se neeche utro, hamesha us child mein jo same value rakhta ho — O(log n).

JAVAch09/MinSegmentTree.java

1/** minq(a, b), 0-indexed and inclusive. Long.MAX_VALUE is the identity for min. */2long min(int a, int b) {3    a += n; b += n;4    long m = Long.MAX_VALUE;5    while (a <= b) {6        if (a % 2 == 1) m = Math.min(m, tree[a++]);7        if (b % 2 == 0) m = Math.min(m, tree[b--]);8        a /= 2; b /= 2;9    }10    return m;11}

/** minq(a, b), 0-indexed and inclusive. Long.MAX_VALUE is the identity for min. */
long min(int a, int b) {
    a += n; b += n;
    long m = Long.MAX_VALUE;
    while (a <= b) {
        if (a % 2 == 1) m = Math.min(m, tree[a++]);
        if (b % 2 == 0) m = Math.min(m, tree[b--]);
        a /= 2; b /= 2;
    }
    return m;
}

JAVAch09/MinSegmentTree.java

1/** Position of a smallest element: walk down from the root into a child that holds the same minimum. */2int argmin() {3    int k = 1;4    while (k < n) {5        k = tree[2 * k] == tree[k] ? 2 * k : 2 * k + 1;6    }7    return k - n;8}

/** Position of a smallest element: walk down from the root into a child that holds the same minimum. */
int argmin() {
    int k = 1;
    while (k < n) {
        k = tree[2 * k] == tree[k] ? 2 * k : 2 * k + 1;
    }
    return k - n;
}

Java noteJava note

Identity values. Start a sum at 0, a min at Long.MAX_VALUE, a max at Long.MIN_VALUE, a gcd at 0, and a xor at 0.

Arrays that aren’t a power of two. Padding with identity values up to the next power of two always works. As a bonus, for commutative operations like sum and min, this exact bottom-up code is correct for any n without padding (SegmentTree.java tests this on random sizes). The tree-walking argmin does need the padded, perfect tree.

Identity values. Sum 0 se shuru karo, min Long.MAX_VALUE se, max Long.MIN_VALUE se, gcd 0 se, aur xor 0 se.

Power of two nahi hai toh? Agle power of two tak identity values se pad kar do — yeh hamesha chalta hai. Bonus: sum aur min jaise commutative operations ke liye yahi bottom-up code kisi bhi n pe bina padding ke sahi chalta hai (SegmentTree.java random sizes pe yeh test karta hai). Par tree mein neeche utarne wale argmin ko padded, perfect tree hi chahiye.

Dynamic queries
Fenwick tree: build	O(n)	or O(n log n) with n adds
Fenwick tree: sum(k), add(k, x)	O(log n)	sums only (invertible ops)
Segment tree: build	O(n)	bottom-up, 2n memory
Segment tree: query, update	O(log n)	any associative op
Min segment tree: argmin	O(log n)	walk down from the root

My notesMere notes

I understand 9.3 — mark as done9.3 samajh aa gaya — done mark karo

9.4Additional techniques

Index compression

Array-based structures need indices 0, 1, 2, …. What if the indices are huge, like 10⁹? An array that size would never fit in memory. If you know all the indices in advance, you can compress them: replace each index x with c(x), its rank among the distinct indices. The order stays the same, so if a < b then c(a) < c(b), and every query still makes sense.

For example, the indices 555, 10⁹ and 8 become c(8) = 1, c(555) = 2, c(10⁹) = 3.

Array-based structures ko indices 0, 1, 2, … chahiye. Par agar indices bahut bade hon, jaise 10⁹? Itna bada array memory mein kabhi fit nahi hoga. Agar saare indices pehle se pata hon, toh unhe compress kar sakte ho: har index x ko c(x) se replace karo — yaani distinct indices mein uski rank. Order wahi rehta hai (a < b toh c(a) < c(b)), isliye har query ka matlab bhi wahi rehta hai.

Jaise indices 555, 10⁹ aur 8 ban jaate hain c(8) = 1, c(555) = 2, c(10⁹) = 3.

JAVAch09/IndexCompression.java

1/** c(x) = rank of x among the distinct values, starting from 1 like the book. */2static int[] compress(int[] xs) {3    int[] sorted = Arrays.stream(xs).distinct().sorted().toArray();4    int[] c = new int[xs.length];5    for (int i = 0; i < xs.length; i++) {6        c[i] = Arrays.binarySearch(sorted, xs[i]) + 1;7    }8    return c;9}

/** c(x) = rank of x among the distinct values, starting from 1 like the book. */
static int[] compress(int[] xs) {
    int[] sorted = Arrays.stream(xs).distinct().sorted().toArray();
    int[] c = new int[xs.length];
    for (int i = 0; i < xs.length; i++) {
        c[i] = Arrays.binarySearch(sorted, xs[i]) + 1;
    }
    return c;
}

VisualiserIndex compression

Values

current
being read
query range

original values x

01234570000309999993051270000

c(x)

012345

1/9

Values as large as 999999 can't be array indices. But only their order matters, so we replace each with its rank.

1/** c(x) = rank of x among the distinct values, starting from 1 like the book. */2static int[] compress(int[] xs) {3    int[] sorted = Arrays.stream(xs).distinct().sorted().toArray();4    int[] c = new int[xs.length];5    for (int i = 0; i < xs.length; i++) {6        c[i] = Arrays.binarySearch(sorted, xs[i]) + 1;7    }8    return c;9}

Range updates with a difference array

Now flip the problem: update a whole range (add x to every value in [a, b]) and read single values. Build a difference array d, where d[k] = arr[k] − arr[k − 1]. The original array is the prefix-sum array of d.

For arr = [3, 3, 1, 1, 1, 5, 2, 2], d = [3, 0, −2, 0, 0, 4, −3, 0]. For instance, arr[6] = 2 = 3 − 2 + 4 − 3.

To add x to [a, b], change just two cells: d[a] += x and d[b + 1] −= x. The first raises every prefix sum from a on, and the second cancels the rise after b. Adding 5 to positions 1–4 turns d into [3, 5, −2, 0, 0, −1, −3, 0].

So range updates become point updates on d, and reading a value is a prefix sum of d. Put d in a Fenwick tree and both operations are O(log n).

Ab problem ulta karo: poori range update karo ([a, b] ki har value mein x jodo) aur single values padho. Ek difference array d banao, jahan d[k] = arr[k] − arr[k − 1]. Original array, d ka prefix-sum array hai.

arr = [3, 3, 1, 1, 1, 5, 2, 2] ke liye d = [3, 0, −2, 0, 0, 4, −3, 0]. Jaise arr[6] = 2 = 3 − 2 + 4 − 3.

[a, b] mein x jodne ke liye sirf do cells badlo: d[a] += x aur d[b + 1] −= x. Pehla a se aage ke har prefix sum ko badha deta hai, doosra b ke baad us badhat ko cancel kar deta hai. Positions 1–4 mein 5 jodo, toh d ban jaata hai [3, 5, −2, 0, 0, −1, −3, 0].

Matlab range update = d pe point update, aur value padhna = d ka prefix sum. d ko Fenwick tree mein daal do — dono operations O(log n).

JAVAch09/RangeUpdates.java

1/** d[0] = arr[0], d[k] = arr[k] - arr[k - 1] */2static long[] difference(int[] arr) {3    long[] d = new long[arr.length];4    for (int k = 0; k < arr.length; k++) {5        d[k] = arr[k] - (k > 0 ? arr[k - 1] : 0);6    }7    return d;8}9 10/** Adds x to every arr[a..b] by touching just two cells of d. */11static void rangeAdd(long[] d, int a, int b, long x) {12    d[a] += x;13    if (b + 1 < d.length) d[b + 1] -= x;14}15 16/** The original array is the prefix-sum array of d. */17static long[] restore(long[] d) {18    long[] arr = new long[d.length];19    for (int k = 0; k < d.length; k++) {20        arr[k] = (k > 0 ? arr[k - 1] : 0) + d[k];21    }22    return arr;23}

/** d[0] = arr[0], d[k] = arr[k] - arr[k - 1] */
static long[] difference(int[] arr) {
    long[] d = new long[arr.length];
    for (int k = 0; k < arr.length; k++) {
        d[k] = arr[k] - (k > 0 ? arr[k - 1] : 0);
    }
    return d;
}

/** Adds x to every arr[a..b] by touching just two cells of d. */
static void rangeAdd(long[] d, int a, int b, long x) {
    d[a] += x;
    if (b + 1 < d.length) d[b + 1] -= x;
}

/** The original array is the prefix-sum array of d. */
static long[] restore(long[] d) {
    long[] arr = new long[d.length];
    for (int k = 0; k < d.length; k++) {
        arr[k] = (k > 0 ? arr[k - 1] : 0) + d[k];
    }
    return arr;
}

VisualiserDifference array: range update in O(1)

Show

Array

query range
added (+)
subtracted (−)
just written

arr

0123456733111522+5

d (difference array)

0123456730-2004-30

1/12

Goal: add 5 to every value in arr[1..4]. Doing it directly touches 4 cells; with d it takes two.

1/** d[0] = arr[0], d[k] = arr[k] - arr[k - 1] */2static long[] difference(int[] arr) {3    long[] d = new long[arr.length];4    for (int k = 0; k < arr.length; k++) {5        d[k] = arr[k] - (k > 0 ? arr[k - 1] : 0);6    }7    return d;8}9 10/** Adds x to every arr[a..b] by touching just two cells of d. */11static void rangeAdd(long[] d, int a, int b, long x) {12    d[a] += x;13    if (b + 1 < d.length) d[b + 1] -= x;14}15 16/** The original array is the prefix-sum array of d. */17static long[] restore(long[] d) {18    long[] arr = new long[d.length];19    for (int k = 0; k < d.length; k++) {20        arr[k] = (k > 0 ? arr[k - 1] : 0) + d[k];21    }22    return arr;23}

a: 1
b: 4
x: 5

JAVARange add + point query with a Fenwick tree

1/** Range add + point query, both O(log n): a Fenwick tree over the difference array (1-indexed). */2static class RangeAddPointQuery {3    final FenwickTree bit;4 5    RangeAddPointQuery(int n) {6        bit = new FenwickTree(n + 1); // room for position b + 1 = n + 17    }8 9    void rangeAdd(int a, int b, long x) {10        bit.add(a, x);11        bit.add(b + 1, -x);12    }13 14    long get(int k) {15        return bit.sum(k); // arr[k] = d[1] + ... + d[k]16    }17}

/** Range add + point query, both O(log n): a Fenwick tree over the difference array (1-indexed). */
static class RangeAddPointQuery {
    final FenwickTree bit;

    RangeAddPointQuery(int n) {
        bit = new FenwickTree(n + 1); // room for position b + 1 = n + 1
    }

    void rangeAdd(int a, int b, long x) {
        bit.add(a, x);
        bit.add(b + 1, -x);
    }

    long get(int k) {
        return bit.sum(k); // arr[k] = d[1] + ... + d[k]
    }
}

Choosing the right structure

You need	Use	Build	Query	Update
Static range sums	Prefix sums	O(n)	O(1)	rebuild O(n)
Static rectangle sums	2D prefix sums	O(R·C)	O(1)	rebuild
Static min / max / gcd	Sparse table	O(n log n)	O(1)	rebuild
Point update + range sum	Fenwick tree	O(n)	O(log n)	O(log n)
Point update + range min/max/any op	Segment tree	O(n)	O(log n)	O(log n)
Range add + point query	Fenwick tree on `d`	O(n)	O(log n)	O(log n)
Range add + range sum	Lazy segment tree (ch. 28)	O(n)	O(log n)	O(log n)

Tumhe chahiye	Use karo	Build	Query	Update
Static range sums	Prefix sums	O(n)	O(1)	dobara O(n)
Static rectangle sums	2D prefix sums	O(R·C)	O(1)	dobara
Static min / max / gcd	Sparse table	O(n log n)	O(1)	dobara
Point update + range sum	Fenwick tree	O(n)	O(log n)	O(log n)
Point update + range min/max/koi bhi op	Segment tree	O(n)	O(log n)	O(log n)
Range add + point query	`d` pe Fenwick tree	O(n)	O(log n)	O(log n)
Range add + range sum	Lazy segment tree (ch. 28)	O(n)	O(log n)	O(log n)

My notesMere notes

I understand 9.4 — mark as done9.4 samajh aa gaya — done mark karo

Range queries

What you will learnIs chapter mein kya seekhoge

9.1Static array queries

Sum queries: prefix sums

Two-dimensional prefix sums

Minimum queries: the sparse table

9.2Binary indexed tree

Structure

Implementation: `k & -k`

9.3Segment tree

Structure

Implementation: a tree inside an array

Other queries

9.4Additional techniques

Index compression

Range updates with a difference array

Choosing the right structure

Cheat sheet

Prefix sums

2D prefix sums

Sparse table

Fenwick tree

Segment tree (bottom-up)

Other operations

Index compression

Difference array

Which one?

Check yourselfKhud ko check karo

Practice on CSESCSES pe practice karo

9.1Static array queries

Sum queries: prefix sums

Two-dimensional prefix sums

Minimum queries: the sparse table

9.2Binary indexed tree

Structure

Implementation: k & -k

9.3Segment tree

Structure

Implementation: a tree inside an array

Other queries

9.4Additional techniques

Index compression

Range updates with a difference array

Choosing the right structure

Cheat sheet

Prefix sums

2D prefix sums

Sparse table

Fenwick tree

Segment tree (bottom-up)

Other operations

Index compression

Difference array

Which one?

Check yourselfKhud ko check karo

Practice on CSESCSES pe practice karo

Implementation: `k & -k`