Range Extremum Queries and Algorithmic Choices

Range Maximum/Minimum Query (RMQ) problems involve processing an array of size n to handle multiple range queries and bulk modifications. Different data structures offer varying trade-offs:

• Brute Force: Simple implementation suitable for small datasets, but query performance is poor.
• Binary Indexed Tree (BIT): Efficient updates and queries, but primarily handles prefix sums. Adapting it for arbitrary range extremum queries lacks flexibility.
• Sparse Table: Excellent for static data where elements remain unchanged after preprocessing. It struggles with frequent online modifications.
• Segment Tree: Provides efficient O(log n) updates and queries for dynamic data. The primary drawback is implementation complexity and verbosity.

Architecture of the Segment Tree

A segment tree is a binary tree where each leaf node represents a single element, and internal nodes represent an aggregation of their children's intervals. The root node spans the entire array. When maintaining a range, a parent's statistical metric (like sum or maximum) must be derivable from its children's metrics, meaning the data must be mergeable.

Consider an array mapped to the interval [1, 6]. The root covers [1, 6]. Its left child covers [1, 3] and its right child covers [4, 6]. If the maximum of [1, 3] is 7 and [4, 6] is 2, the maximum of [1, 6] is easily computed as max(7, 2) = 7.

Memory Allocation

Segment trees are typically stored in an array. Because the structure is a balanced binary tree, the worst-case space requirement is 4 times the original array size. For a node at index i, its children reside at i * 2 (or i << 1) and i * 2 + 1 (or i << 1 | 1). Bitwise operations can accelerate these calculations.

struct Node {
    long long val;
    long long lazy;
} seg[MAX_SIZE << 2];
long long arr[MAX_SIZE];

Tree Construction

Building the tree involves recursively splitting the interval until leaf nodes are reached. After initializing the leaves, the parent nodes aggregate the results from their children using a pull operation.

void pull(int idx) {
    seg[idx].val = seg[idx << 1].val + seg[idx << 1 | 1].val;
}

void build(int l, int r, int idx) {
    if (l == r) {
        seg[idx].val = arr[l];
        seg[idx].lazy = 0;
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, idx << 1);
    build(mid + 1, r, idx << 1 | 1);
    pull(idx);
}

The construction phase operates in O(n log n) time.

Range Querying

Querying utilizes a recursive binary search. If the current node's interval is fully contained within the query bounds, its precomputed value is returned immediately. Otherwise, the search branches to the children, and the results are summed.

long long query(int l, int r, int ql, int qr, int idx) {
    if (ql <= l && r <= qr) {
        return seg[idx].val;
    }
    int mid = (l + r) >> 1;
    long long res = 0;
    if (ql <= mid) res += query(l, mid, ql, qr, idx << 1);
    if (qr > mid) res += query(mid + 1, r, ql, qr, idx << 1 | 1);
    return res;
}

Single-point queries can be executed by setting ql equal to qr.

Range Updates and Lazy Propagation

Applying updates to every leaf node for range modifications degrades performance to O(n). Lazy propagation optimizes this by deferring updates until a query necessitates them. When a range update fully covers a node's interval, the modification is applied to the node, and a lazy tag records the pending change without immediately descending to the children.

Before traversing into children during subsequent queries or updates, the push function distributes the pending lazy tag down one level, updating the children's values and inheriting the tag.

void push(int idx, int left_len, int right_len) {
    if (seg[idx].lazy) {
        seg[idx << 1].lazy += seg[idx].lazy;
        seg[idx << 1 | 1].lazy += seg[idx].lazy;
        seg[idx << 1].val += left_len * seg[idx].lazy;
        seg[idx << 1 | 1].val += right_len * seg[idx].lazy;
        seg[idx].lazy = 0;
    }
}

void update(int l, int r, int ql, int qr, long long add_val, int idx) {
    if (ql <= l && r <= qr) {
        seg[idx].val += (r - l + 1) * add_val;
        seg[idx].lazy += add_val;
        return;
    }
    int mid = (l + r) >> 1;
    push(idx, mid - l + 1, r - mid);
    if (ql <= mid) update(l, mid, ql, qr, add_val, idx << 1);
    if (qr > mid) update(mid + 1, r, ql, qr, add_val, idx << 1 | 1);
    pull(idx);
}

Complete Implementation

The following code demonstrates a full segment tree implementation supporting range addition and range sum queries.

#include <iostream>

using namespace std;
typedef long long ll;

const int MAXN = 200005;
ll data[MAXN];
ll seg[MAXN << 2];
ll mark[MAXN << 2];

void pull(int idx) {
    seg[idx] = seg[idx << 1] + seg[idx << 1 | 1];
}

void push(int idx, int left_len, int right_len) {
    if (mark[idx]) {
        mark[idx << 1] += mark[idx];
        mark[idx << 1 | 1] += mark[idx];
        seg[idx << 1] += left_len * mark[idx];
        seg[idx << 1 | 1] += right_len * mark[idx];
        mark[idx] = 0;
    }
}

void build(int l, int r, int idx) {
    if (l == r) {
        seg[idx] = data[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, idx << 1);
    build(mid + 1, r, idx << 1 | 1);
    pull(idx);
}

void update_range(int l, int r, int ql, int qr, ll val, int idx) {
    if (ql <= l && r <= qr) {
        seg[idx] += (r - l + 1) * val;
        mark[idx] += val;
        return;
    }
    int mid = (l + r) >> 1;
    push(idx, mid - l + 1, r - mid);
    if (ql <= mid) update_range(l, mid, ql, qr, val, idx << 1);
    if (qr > mid) update_range(mid + 1, r, ql, qr, val, idx << 1 | 1);
    pull(idx);
}

ll query_range(int l, int r, int ql, int qr, int idx) {
    if (ql <= l && r <= qr) return seg[idx];
    int mid = (l + r) >> 1;
    push(idx, mid - l + 1, r - mid);
    ll res = 0;
    if (ql <= mid) res += query_range(l, mid, ql, qr, idx << 1);
    if (qr > mid) res += query_range(mid + 1, r, ql, qr, idx << 1 | 1);
    return res;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &data[i]);
    build(1, n, 1);
    while (m--) {
        int op;
        scanf("%d", &op);
        if (op == 1) {
            int x, y; ll k;
            scanf("%d %d %lld", &x, &y, &k);
            update_range(1, n, x, y, k, 1);
        } else {
            int x, y;
            scanf("%d %d", &x, &y);
            printf("%lld\n", query_range(1, n, x, y, 1));
        }
    }
    return 0;
}