---
tags: Data Structure
title: Segment Tree
---

## Range Minimum (Maximum) Query

class SegmentTree {
public:
    SegmentTree(size_t size) : N(size), arr(size << 2, 0), tag(size << 2, 0) {}

    int query(int left, int right) {
        return query(1, 1, N, left, right);
    }

    void modify(int left, int right, int val) {
        modify(1, 1, N, left, right - 1, val);
    }

private:
    inline int left(int x) { return x << 1; }
    inline int right(int x) { return (x << 1) | 1;}
    
    inline void push(int x) {
        tag[left(x)] += tag[x];
        tag[right(x)] += tag[x];
        arr[x] += tag[x];
        tag[x] = 0;
    }

    int query(int x, int L, int R, int ql, int qr) {
        if (ql == L && qr == R) {
            return arr[x] + tag[x];
        }
        push(x);
        int M = (L + R) >> 1;
        if (qr <= M) {
            return query(left(x), L, M, ql, qr);
        }
        else if (ql > M) {
            return query(right(x), M + 1, R, ql, qr);
        }
        else {
            return max(query(left(x), L, M, ql, M), 
                       query(right(x), M + 1, R, M + 1, qr));
        }
    }

    void modify(int x, int L, int R, int ml, int mr, int val) {
        if (ml == L && mr == R) {
            tag[x] += val;
            return;
        }

        int M = (L + R) >> 1;
        if (mr <= M) {
            modify(left(x), L, M, ml, mr, val);
        }
        else if (ml > M) {
            modify(right(x), M + 1, R, ml, mr, val);
        }
        else {
            modify(left(x), L, M, ml, M, val);
            modify(right(x), M + 1, R, M + 1, mr, val);
        }
        arr[x] = max(arr[left(x)] + tag[left(x)], 
                     arr[right(x)] + tag[right(x)]);
    }

    size_t N;
    vector<int> arr;
    vector<int> tag;
};

## Range Sum Query

class SegmentTree {
public:
    SegmentTree(const vector<int>& that)
        : N(that.size()), arr(that.size() << 2, 0), tag(that.size() << 2, 0) {
        build(1, 1, N, that);
    }

    void modify(int left, int right, int val) {
        modify(1, 1, N, left, right, val);
    }

    ll query(int left, int right) {
        return query(1, 1, N, left, right);
    }

private:
    inline int left(int x) { return x << 1; }
    inline int right(int x) { return (x << 1) | 1;}
    
    ll build(int x, int L, int R, const vector<int>& that) {
        if (L == R) {
            return arr[x] = that[L - 1];
        }

        int M = (L + R) >> 1;
        return arr[x] = build(left(x), L, M, that) + 
                        build(right(x), M + 1, R, that);
    }

    inline ll calculate(int x, int L, int R) {
        return arr[x] + tag[x] * (R - L + 1);
    }
    

    inline void push(int x, int L, int R) {
        tag[left(x)] += tag[x];
        tag[right(x)] += tag[x];
        arr[x] = calculate(x, L, R);
        tag[x] = 0;
    }

    ll query(int x, int L, int R, int ql, int qr) {
        if (ql == L && qr == R) {
            return calculate(x, L, R);
        }
        push(x, L, R);
        int M = (L + R) >> 1;
        if (qr <= M) {
            return query(left(x), L, M, ql, qr);
        }
        else if (ql > M) {
            return query(right(x), M + 1, R, ql, qr);
        }
        else {
            return query(left(x), L, M, ql, M) + 
                    query(right(x), M + 1, R, M + 1, qr);
        }
    }

    void modify(int x, int L, int R, int ml, int mr, int val) {
        if (ml == L && mr == R) {
            tag[x] += val;
            return;
        }

        int M = (L + R) >> 1;
        if (mr <= M) {
            modify(left(x), L, M, ml, mr, val);
        }
        else if (ml > M) {
            modify(right(x), M + 1, R, ml, mr, val);
        }
        else {
            modify(left(x), L, M, ml, M, val);
            modify(right(x), M + 1, R, M + 1, mr, val);
        }

        arr[x] = calculate(left(x), L, M) + calculate(right(x), M + 1, R);
    }

    size_t N;
    vector<ll> arr;
    vector<ll> tag;
};