Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Range Query Revision
DSA

Range Query Revision

Quickly revise the main data structures and techniques used for efficient range queries.

1 Fenwick Tree (Binary Indexed Tree)

update(i, d):  while i <= n:  tree[i] += d;   i += i & -i

query(i):      s = 0
               while i > 0:  s += tree[i];  i -= i & -i

range(l, r) = query(r) - query(l - 1)

Key idea: i & -i isolates the lowest set bit — the size of the block tree[i] owns.

Time: O(log n) per operation. Indices are 1-based.

public void add(int i, int d) {
    for (; i <= n; i += i & -i) tree[i] += d;
}

public int prefix(int i) {
    int s = 0;
    for (; i > 0; i -= i & -i) s += tree[i];
    return s;
}
def add(self, i, d):
    while i <= self.n:
        self.tree[i] += d
        i += i & -i

def prefix(self, i):
    s = 0
    while i > 0:
        s += self.tree[i]
        i -= i & -i
    return s
void add(int i, int d) {
    for (; i <= n; i += i & -i) tree[i] += d;
}

int prefix(int i) {
    int s = 0;
    for (; i > 0; i -= i & -i) s += tree[i];
    return s;
}
add(i, d) {
  for (; i <= this.n; i += i & -i) this.tree[i] += d;
}

prefix(i) {
  let s = 0;
  for (; i > 0; i -= i & -i) s += this.tree[i];
  return s;
}

2 Sparse Table (Immutable Range Min)

build: sp[0] = arr
       sp[j][k] = min(sp[j-1][k], sp[j-1][k + 2^(j-1)])

query(l, r): k = floor(log2(r - l + 1))
             return min(sp[k][l], sp[k][r - 2^k + 1])

Key idea: two overlapping power-of-two blocks cover any range — overlap is harmless for idempotent ops (min, max, gcd).

Time: build O(n log n), query O(1), no updates.

public int query(int l, int r) {
    int j = 31 - Integer.numberOfLeadingZeros(r - l + 1);
    return Math.min(sp[j][l], sp[j][r - (1 << j) + 1]);
}
def query(self, l, r):
    j = (r - l + 1).bit_length() - 1
    return min(self.sp[j][l], self.sp[j][r - (1 << j) + 1])
int query(int l, int r) {
    int j = std::__lg(r - l + 1);
    return min(sp[j][l], sp[j][r - (1 << j) + 1]);
}
query(l, r) {
  const j = 31 - Math.clz32(r - l + 1);
  return Math.min(this.sp[j][l], this.sp[j][r - (1 << j) + 1]);
}

3 Choosing Checklist

  • Updates needed? → Fenwick (sums) or segment tree (anything else)
  • Truly static? → prefix sum or sparse table
  • Sum with updates? → Fenwick beats segment tree on code size
  • Min/max with updates? → segment tree only

My Private Notes

Notes are auto-saved locally to this device.