Template. Segment Tree

區間查詢最大值線段樹，支援單點、範圍修改，使用Lazy flag優化。

Code

#define maxn 1000
struct node {
    int data, lazy;
}tree[maxn * 4];
int num[maxn];
// root = 0
int make_tree(int l, int r, int index) {
    tree[index].lazy = 0;
    if (l == r)
        return tree[index].data = num[l];
    int m = (l + r) >> 1;
    int index2 = index << 1;
    return tree[index].data = max(make_tree(l, m, index2 + 1), make_tree(m + 1, r, index2 + 2));
}
int query(int l, int r, int s, int e, int index) {
    if (l > e || r < s)
        return -10000000;
    if (s <= l && r <= e)
        return tree[index].data + tree[index].lazy;
    int m = (l + r) >> 1;
    int index2 = index << 1;
    return max(query(l, m, s, e, index2 + 1), query(m + 1, r, s, e, index2 + 2)) + tree[index].lazy;
}
void modify(int l, int r, int s, int e, int index, int dx) {
    if (l > e || r < s)
        return;
    if (s <= l && r <= e)
        tree[index].lazy += dx;
    else {
        int m = (l + r) >> 1;
        int index2 = index << 1;
        modify(l, m, s, e, index2 + 1, dx);
        modify(m + 1, r, s, e, index2 + 2, dx);
        tree[index].data = max(tree[index2 + 1].data + tree[index2 + 1].lazy,
                               tree[index2 + 2].data + tree[index2 + 2].lazy);
    }
}