CodeMosa

Master LeetCode Patterns

AdvancedAdvanced Patterns

Range Queries

Segment trees, Fenwick trees, and offline tricks for range updates/queries

Time: O(log n) per op
Space: O(n)

What is Range Queries?

#
Definition: Answer many range queries and updates efficiently using segment trees, Fenwick trees, or offline reordering.

Core Idea

#

Build tree structures over arrays to aggregate ranges and support point/range updates efficiently.

When to Use

#

Use when many queries/updates over ranges; consider offline methods (Mo's algorithm) when applicable.

How Range Queries works

#

Segment tree with lazy propagation for range updates/queries, Fenwick tree for prefix sums; offline Mo's algorithm for static queries.

  • Range sum/min/max
  • Point/range updates
  • Many queries

Range Queries vs alternatives

#

Use this pattern when use when many queries/updates over ranges; consider offline methods (mo's algorithm) when applicable.

Segment TreeFenwick Tree (Binary Indexed Tree)

General Recognition Cues

#
General indicators that this pattern might be applicable
  • Range sum/min/max
  • Point/range updates
  • Many queries

Related Collections

#
Curated practice sets for this pattern
Segment Tree Practice ProblemsFenwick Tree (BIT) Practice Problems

Code Templates

#
Segment tree with lazy propagation for range updates/queries, Fenwick tree for prefix sums; offline Mo's algorithm for static queries.
# Design Template (LRU Cache)
class LRUCache:
    def __init__(self, capacity: int):
        from collections import OrderedDict
        self.cap=capacity; self.od=OrderedDict()
    def get(self, key:int)->int:
        if key not in self.od: return -1
        self.od.move_to_end(key)
        return self.od[key]
    def put(self, key:int, value:int)->None:
        self.od[key]=value; self.od.move_to_end(key)
        if len(self.od)>self.cap: self.od.popitem(last=False)

Pattern Variants & Approaches

#
Different methodologies and implementations for this pattern
1

Segment Tree

#

Tree over ranges with lazy propagation

When to Use This Variant
  • Range updates
Use Case
Sum/min/max
Advantages
  • O(log n)
  • Flexible
Implementation
class SegTree:
    def __init__(self, arr):
        n=len(arr); self.n=1
        while self.n<n: self.n<<=1
        self.t=[0]*(2*self.n)
        for i,v in enumerate(arr): self.t[self.n+i]=v
        for i in range(self.n-1,0,-1): self.t[i]=self.t[i<<1]+self.t[i<<1|1]
    def update(self, idx, val):
        i=self.n+idx; self.t[i]=val
        i>>=1
        while i: self.t[i]=self.t[i<<1]+self.t[i<<1|1]; i>>=1
    def query(self, l, r):
        l+=self.n; r+=self.n+1; res=0
        while l<r:
            if l&1: res+=self.t[l]; l+=1
            if r&1: r-=1; res+=self.t[r]
            l>>=1; r>>=1
        return res
2

Fenwick Tree

#

Binary indexed tree for prefix sums

When to Use This Variant
  • Prefix updates
Use Case
Sum/freq
Advantages
  • O(log n)
  • Compact
Implementation
class Fenwick:
    def __init__(self, n): self.n=n; self.bit=[0]*(n+1)
    def add(self, i, delta):
        i+=1
        while i<=self.n: self.bit[i]+=delta; i+=i&-i
    def sum(self, i):
        i+=1; s=0
        while i>0: s+=self.bit[i]; i-=i&-i
        return s
    def range_sum(self, l, r): return self.sum(r)-self.sum(l-1)
3

Offline Tricks

#

Mo's algorithm / sorting queries

When to Use This Variant
  • Reorder queries
Use Case
Answer without updates
Advantages
  • Competitive in practice
Implementation
# Mo's algorithm skeleton
def mos_algorithm(arr, queries):
    import math
    n=len(arr); B=int(math.sqrt(n))
    queries=sorted(queries, key=lambda q: (q[0]//B, q[1] if (q[0]//B)%2==0 else -q[1]))
    curL=curR=0; curAns=0; ans=[0]*len(queries)
    def add(i):
        nonlocal curAns
        curAns += arr[i]
    def remove(i):
        nonlocal curAns
        curAns -= arr[i]
    for idx,(L,R) in enumerate(queries):
        while curL>L: curL-=1; add(curL)
        while curR<=R: add(curR); curR+=1
        while curL<L: remove(curL); curL+=1
        while curR>R+1: curR-=1; remove(curR)
        ans[idx]=curAns
    return ans

Common Pitfalls

#
Watch out for these common mistakes
  • Indexing 0/1-based confusion
  • Lazy propagation bugs
  • Memory size 4n

Related Patterns

#
Segment TreeFenwick Tree (Binary Indexed Tree)

Example Problems

#
Classic LeetCode problems using this pattern

Complexity Analysis

#
Time Complexity
O(log n) per op

Tree height log n.

Space Complexity
O(n)

Tree nodes ~4n.

Ready to test your knowledge?

Test your pattern recognition with interactive questions