Skip to content

Offline Range Queries

So far the monotonic stack processed the full array and answered one global question: the next greater element for every index, the largest rectangle overall, etc. But what if you have Q queries, each asking about a different subarray [L, R]?

The Naive Approach

For each query [L, R], build a fresh monotonic stack on A[L..R] and extract the answer. Each build is O(R - L + 1), worst case O(N). If you have Q queries, that's O(NQ) total. When both N and Q are 10^5, you're looking at 10^10 operations. Way too slow.

You might think: can we precompute something? But the monotonic stack's contents depend on which subarray you're looking at. The stack for [0, 7] isn't a simple restriction of the stack for [0, 10]. Elements that survive in the longer range might get eclipsed in the shorter one. So precomputation isn't obvious.

The Offline Trick

Here's the key idea: sort queries by their right endpoint R. Then sweep through the array left to right, maintaining your monotonic stack. When you reach index R, pause and answer every query that ends at R.

Why does this help? Because the monotonic stack at position R already encodes information about which elements have survived up to that point. For a query [L, R], the answer involves only those survivors with index >= L.

The sweep ensures each element is pushed and popped at most once across the entire run. You're not rebuilding the stack per query — you're building it once, and queries piggyback on the sweep.

The Data Structure Bridge

But here's the gap: the stack tells you which elements survived, but it can't efficiently answer "how many survivors have index >= L?" The stack is, well, a stack. It doesn't support range queries.

You need a companion data structure. Enter the Fenwick Tree (Binary Indexed Tree), indexed by position in the original array:

  • When you push index i onto the stack, do bit.update(i, +1) — mark it active.
  • When you pop index j off the stack, do bit.update(j, -1) — mark it inactive.
  • For a query [L, R], compute bit.query(L, R) — count active elements in that range.

The Fenwick Tree turns the stack's "I know who's alive" into "I can count who's alive in any range" in O(log N) per operation.

This is the pattern: the stack handles the logic (who eclipses whom), and the BIT handles the bookkeeping (how many survivors in a range).

Walking Through an Example

Array: [3, 1, 4, 1, 5, 9, 2, 6] (indices 0-7). We'll maintain a decreasing stack and count "stack survivors" — elements that would remain on a decreasing stack built over [L, R].

Queries: (1, 4), (2, 7), (0, 5). Sorted by R: (1, 4), (0, 5), (2, 7).

i=0, val=3: Stack empty. Push 0. BIT: activate 0. Stack: [0].

i=1, val=1: 1 < 3, no pop. Push 1. Activate 1. Stack: [0, 1].

i=2, val=4: Pop 1 (val 1 <= 4), deactivate 1. Pop 0 (val 3 <= 4), deactivate 0. Push 2. Activate 2. Stack: [2].

i=3, val=1: 1 < 4, no pop. Push 3. Activate 3. Stack: [2, 3].

i=4, val=5: Pop 3 (val 1 <= 5), deactivate 3. Pop 2 (val 4 <= 5), deactivate 2. Push 4. Activate 4. Stack: [4].

Answer query (1, 4): bit.query(1, 4) = count of active elements in [1, 4]. Only index 4 is active. Answer: 1.

i=5, val=9: Pop 4 (val 5 <= 9), deactivate 4. Push 5. Activate 5. Stack: [5].

Answer query (0, 5): bit.query(0, 5) = count of active in [0, 5]. Only index 5 is active. Answer: 1.

i=6, val=2: 2 < 9, no pop. Push 6. Activate 6. Stack: [5, 6].

i=7, val=6: Pop 6 (val 2 <= 6), deactivate 6. Push 7. Activate 7. Stack: [5, 7].

Answer query (2, 7): bit.query(2, 7) = count of active in [2, 7]. Indices 5 and 7 are active. Answer: 2.

Final answers in original order: 1, 2, 1.

Offline sweep — vertical sweep line moves right, queries activate at their right endpoint, Fenwick Tree tracks stack elements

Wait — Is This Correct?

You might be uneasy. The stack at position R reflects a sweep from 0 to R, not from L to R. Elements to the left of L might have popped things that would've survived in a stack built on [L, R] alone.

Think carefully, though. The decreasing stack at position R contains elements that haven't been eclipsed by anything to their right (up to R). If an element at index j (where L <= j <= R) was popped by some later element at index k (where k <= R), that element would also be popped in a stack built purely on [L, R]. The popping depends only on elements to the right, not on elements to the left.

What about elements to the left of L still sitting on the stack? They might be active in the BIT, but our query restricts to [L, R], so they don't get counted. The BIT range query handles this automatically.

So yes, bit.query(L, R) after processing up to R gives exactly the count of elements that would survive a decreasing stack on [L, R].

Complexity

  • Stack operations: Each element is pushed and popped at most once across the entire sweep. That's O(N) total stack operations, each costing O(log N) for the BIT update. Total: O(N log N).
  • Query answering: Each query does one BIT range query: O(log N). Total: O(Q log N).
  • Sorting queries: O(Q log Q).
  • Overall: O((N + Q) log N). Compare that to the naive O(NQ). For N = Q = 10^5, that's 10^5 * 17 vs. 10^{10}. A factor of ~60,000 improvement.

The General Pattern

The sweep + stack + BIT triple isn't limited to counting survivors. You can adapt it to:

  • Sum of survivor values in [L, R] — use BIT that tracks sums instead of counts.
  • Maximum stack depth over a range — trickier, requires a different companion structure.
  • Number of "visible buildings from the right" — same as survivor count on a decreasing stack.

The recipe is always the same: identify the monotonic stack property you care about, sweep with the stack, use a companion data structure to answer range queries about the stack's current state.

Try It

The starter code reads an array and Q queries. For each query [L, R], count the number of "stack survivors" — elements that would remain on a decreasing stack built over [L, R]. The queries are sorted offline by right endpoint. The stack and BIT are wired up, but the key operations (deactivating popped elements, activating pushed elements, and querying the BIT for answers) are left for you to fill in.

The BIT is already implemented. Focus on the integration: making the stack and BIT talk to each other. Every push means an activation. Every pop means a deactivation. Every query means a range count. That's the whole pattern.