Overview

Given an array \(A\), the problem asks us to quickly answer the range maximum \(\max(A_L,\dots,A_R)\) for each query \((L,R)\). To process a large number of range maximum queries, we use a segment tree.

Analysis

If we scan the interval \([L,R]\) from the beginning to find the maximum for each query, it takes \(O(R-L+1)\) per query. In the worst case, this is \(O(N)\) per query, resulting in \(O(NQ)\) overall.

Given the constraints \(N,Q \le 10^5\), for example when \(N=Q=10^5\), this would require around \(10^{10}\) operations, which will not finish within the time limit (TLE).

Therefore, we need to “preprocess the array so that we can answer the maximum of any interval in logarithmic time.” Operations like range maximum, which satisfy the associative property (\(\max(\max(a,b),c)=\max(a,\max(b,c))\)), can be handled with a segment tree.

Algorithm

Segment Tree (Range Maximum)

A segment tree is a complete binary tree that manages the array by dividing it into intervals.

• Leaves: each element \(A_i\)
• Internal nodes: the maximum value of the interval that the node is responsible for

1. Construction (Preprocessing)

Let size be the smallest power of \(2\) that is at least \(N\), and place the array elements at the leaves of the tree (seg[size + i]). Fill the remaining leaves with a sufficiently small value (\(-\infty\)) that does not affect the maximum.

Then, building from the bottom up: - seg[i] = max(seg[2*i], seg[2*i+1])

This fills in the internal nodes up to the root seg[1] with maximum values.

2. Query Processing (Maximum of interval \([L,R]\))

Queries \((L,R)\) are given in 1-indexed form, so we convert to 0-indexed and then shift to leaf positions: - l = (L-1) + size - r = (R-1) + size

Then we collect the minimal set of nodes that cover the interval as follows:

• If l is a right child (odd), then that node is entirely contained in the interval, so we include it in the answer and do l++
• If r is a left child (even), then that node is entirely contained in the interval, so we include it in the answer and do r--
• Then move up to the parent with l //= 2, r //= 2

We repeat this until l > r, which gives us the maximum over exactly the set of nodes covering the interval \([L,R]\). Since we move up one level at each step, the time complexity is \(O(\log N)\).

(Example) Think of it as decomposing \([L,R]\) into intervals of power-of-2 lengths and taking their maximum. The segment tree performs this decomposition automatically.

Complexity

• Time complexity: Construction \(O(N)\), each query \(O(\log N)\), total \(O(N + Q\log N)\)
• Space complexity: Segment tree array \(O(\text{size}) = O(N)\)

Implementation Notes

• Be careful with 1-indexed input: The query values \(L,R\) are 1-indexed, so convert them to L-1, R-1 before processing.

• Make size a power of \(2\): When managing the segment tree as an array, making size a power of \(2\) simplifies the parent-child relationship (children of i are 2i and 2i+1).

• Initial value (identity element): Since we are computing the maximum, use a sufficiently small initial value (-10**18 in the code).

• Fast I/O: Since \(Q\) can be large, using sys.stdin.readline and accumulating output in an array to print all at once at the end is effective.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))

    size = 1
    while size < N:
        size <<= 1

    seg = [-10**18] * (2 * size)
    for i, v in enumerate(A):
        seg[size + i] = v
    for i in range(size - 1, 0, -1):
        left = seg[i * 2]
        right = seg[i * 2 + 1]
        seg[i] = left if left > right else right

    out = []
    for _ in range(Q):
        l, r = map(int, input().split())
        l = l - 1 + size
        r = r - 1 + size
        res = -10**18
        while l <= r:
            if l & 1:
                if seg[l] > res:
                    res = seg[l]
                l += 1
            if not (r & 1):
                if seg[r] > res:
                    res = seg[r]
                r -= 1
            l >>= 1
            r >>= 1
        out.append(str(res))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.