Range minimum with updates – Data Structures Practice

Find the smallest value in part of a list, while the list keeps changing.

What to build

A segment tree that stores minimums instead of sums.

Requirements

M l r prints the smallest of a[l] to a[r].
U i v changes a[i] to v.
Both operations must take O(log n).

Input

The first line has n and q. The second line has the n numbers. Each of the next q lines has one operation. Positions start at 0.

Output

One line for each M.

Constraints

1 ≤ n, q ≤ 1000, 0 ≤ l ≤ r < n, and every value is from −1 000 000 to 1 000 000.

Example

Input:

Output:

5
2
3

Why it works

A segment tree only needs a way to combine the answers of two halves, and "the smaller of the two" works as well as "the sum". Prefix tricks fail here, because one minimum cannot be subtracted from another.

Examples

Example 1 · Input

Expected output

5
2
3

Example 2 · Input

Expected output

Hints

Hint 1

The starter is the lesson's tree of sums. Each node must store the smaller of its two children instead of their total.

Hint 2

A node outside the question must not affect the answer. Returning 0, as the sum tree does, would be wrong.

Hint 3

One way round that: only go into a half that the question actually reaches.

Solution

Show one correct solution (try it yourself first)

#include <stdio.h>

int a[1000], tree[4000];

int smaller(int x, int y) {
    return x < y ? x : y;
}

void build(int node, int lo, int hi) {
    if (lo == hi) {
        tree[node] = a[lo];
        return;
    }
    int mid = (lo + hi) / 2;
    build(2 * node, lo, mid);
    build(2 * node + 1, mid + 1, hi);
    tree[node] = smaller(tree[2 * node], tree[2 * node + 1]);
}

int query(int node, int lo, int hi, int l, int r) {
    if (l <= lo && hi <= r) return tree[node];
    int mid = (lo + hi) / 2;
    if (r <= mid) return query(2 * node, lo, mid, l, r);        /* only the left half is asked about */
    if (l > mid) return query(2 * node + 1, mid + 1, hi, l, r);   /* only the right half */
    return smaller(query(2 * node, lo, mid, l, r), query(2 * node + 1, mid + 1, hi, l, r));
}

void update(int node, int lo, int hi, int i, int value) {
    if (lo == hi) {
        tree[node] = value;
        return;
    }
    int mid = (lo + hi) / 2;
    if (i <= mid) update(2 * node, lo, mid, i, value);
    else update(2 * node + 1, mid + 1, hi, i, value);
    tree[node] = smaller(tree[2 * node], tree[2 * node + 1]);
}

int main(void) {
    int n, q;
    scanf("%d %d", &n, &q);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    build(1, 0, n - 1);
    for (int k = 0; k < q; k++) {
        char op[2];
        int x, y;
        scanf("%1s %d %d", op, &x, &y);
        if (op[0] == 'M') printf("%d\n", query(1, 0, n - 1, x, y));
        else update(1, 0, n - 1, x, y);
    }
    return 0;
}

Lesson: Segment trees and Fenwick trees →