Basic Segment Tree with Lazy Propagation

The fundamental segment tree template maintains range sum with lazy propagation for range addition operations.

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

struct SegNode {
    int left, right;
    int64 sum;
    int64 lazy;
};

class SegmentTree {
private:
    static const int MAXN = 100005;
    vector<SegNode> tree;
    vector<int64> arr;
    int size;
    
    int leftChild(int idx) { return idx << 1; }
    int rightChild(int idx) { return idx << 1 | 1; }
    
    void build(int node, int l, int r) {
        tree[node].left = l;
        tree[node].right = r;
        tree[node].lazy = 0;
        
        if (l == r) {
            tree[node].sum = arr[l];
            return;
        }
        
        int mid = (l + r) >> 1;
        build(leftChild(node), l, mid);
        build(rightChild(node), mid + 1, r);
        tree[node].sum = tree[leftChild(node)].sum + tree[rightChild(node)].sum;
    }
    
    void apply(int node, int64 value) {
        int len = tree[node].right - tree[node].left + 1;
        tree[node].sum += value * len;
        tree[node].lazy += value;
    }
    
    void pushDown(int node) {
        if (tree[node].lazy != 0) {
            apply(leftChild(node), tree[node].lazy);
            apply(rightChild(node), tree[node].lazy);
            tree[node].lazy = 0;
        }
    }
    
    void rangeAdd(int node, int l, int r, int64 value) {
        if (l <= tree[node].left && tree[node].right <= r) {
            apply(node, value);
            return;
        }
        
        pushDown(node);
        int mid = (tree[node].left + tree[node].right) >> 1;
        
        if (l <= mid) rangeAdd(leftChild(node), l, r, value);
        if (r > mid) rangeAdd(rightChild(node), l, r, value);
        
        tree[node].sum = tree[leftChild(node)].sum + tree[rightChild(node)].sum;
    }
    
    int64 rangeQuery(int node, int l, int r) {
        if (l <= tree[node].left && tree[node].right <= r) {
            return tree[node].sum;
        }
        
        pushDown(node);
        int mid = (tree[node].left + tree[node].right) >> 1;
        int64 result = 0;
        
        if (l <= mid) result += rangeQuery(leftChild(node), l, r);
        if (r > mid) result += rangeQuery(rightChild(node), l, r);
        
        return result;
    }
    
public:
    SegmentTree(int n) : size(n) {
        tree.resize(4 * n + 5);
        arr.resize(n + 1);
    }
    
    void initialize(const vector<int64>& data) {
        arr = data;
        build(1, 1, size);
    }
    
    void add(int l, int r, int64 value) {
        rangeAdd(1, l, r, value);
    }
    
    int64 query(int l, int r) {
        return rangeQuery(1, l, r);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    
    vector<int64> input(n + 1);
    for (int i = 1; i <= n; i++) cin >> input[i];
    
    SegmentTree st(n);
    st.initialize(input);
    
    while (q--) {
        int operation;
        cin >> operation;
        if (operation == 1) {
            int x, y;
            int64 k;
            cin >> x >> y >> k;
            st.add(x, y, k);
        } else {
            int x, y;
            cin >> x >> y;
            cout << st.query(x, y) << '\n';
        }
    }
    
    return 0;
}

Segment Tree with Range Multiplication and Addition

This extended version supports both range multiplication and addition operations with lazy propagation.

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

struct Node {
    int l, r;
    int64 sum;
    int64 addTag;
    int64 mulTag;
};

class AdvancedSegmentTree {
private:
    vector<Node> tree;
    int n;
    int64 modulus;
    
    int lc(int idx) { return idx << 1; }
    int rc(int idx) { return idx << 1 | 1; }
    
    void pushUp(int idx) {
        tree[idx].sum = (tree[lc(idx)].sum + tree[rc(idx)].sum) % modulus;
    }
    
    void applyMul(int idx, int64 mulVal) {
        tree[idx].sum = (tree[idx].sum * mulVal) % modulus;
        tree[idx].mulTag = (tree[idx].mulTag * mulVal) % modulus;
        tree[idx].addTag = (tree[idx].addTag * mulVal) % modulus;
    }
    
    void applyAdd(int idx, int64 addVal) {
        int len = tree[idx].r - tree[idx].l + 1;
        tree[idx].sum = (tree[idx].sum + addVal * len) % modulus;
        tree[idx].addTag = (tree[idx].addTag + addVal) % modulus;
    }
    
    void pushDown(int idx) {
        int64 mulVal = tree[idx].mulTag;
        int64 addVal = tree[idx].addTag;
        
        if (mulVal != 1) {
            applyMul(lc(idx), mulVal);
            applyMul(rc(idx), mulVal);
            tree[idx].mulTag = 1;
        }
        
        if (addVal != 0) {
            applyAdd(lc(idx), addVal);
            applyAdd(rc(idx), addVal);
            tree[idx].addTag = 0;
        }
    }
    
    void build(int idx, int l, int r, const vector<int64>& arr) {
        tree[idx].l = l;
        tree[idx].r = r;
        tree[idx].addTag = 0;
        tree[idx].mulTag = 1;
        
        if (l == r) {
            tree[idx].sum = arr[l] % modulus;
            return;
        }
        
        int mid = (l + r) >> 1;
        build(lc(idx), l, mid, arr);
        build(rc(idx), mid + 1, r, arr);
        pushUp(idx);
    }
    
    void updateMul(int idx, int l, int r, int64 val) {
        if (l <= tree[idx].l && tree[idx].r <= r) {
            applyMul(idx, val);
            return;
        }
        pushDown(idx);
        int mid = (tree[idx].l + tree[idx].r) >> 1;
        if (l <= mid) updateMul(lc(idx), l, r, val);
        if (r > mid) updateMul(rc(idx), l, r, val);
        pushUp(idx);
    }
    
    void updateAdd(int idx, int l, int r, int64 val) {
        if (l <= tree[idx].l && tree[idx].r <= r) {
            applyAdd(idx, val);
            return;
        }
        pushDown(idx);
        int mid = (tree[idx].l + tree[idx].r) >> 1;
        if (l <= mid) updateAdd(lc(idx), l, r, val);
        if (r > mid) updateAdd(rc(idx), l, r, val);
        pushUp(idx);
    }
    
    int64 query(int idx, int l, int r) {
        if (l <= tree[idx].l && tree[idx].r <= r) {
            return tree[idx].sum;
        }
        pushDown(idx);
        int mid = (tree[idx].l + tree[idx].r) >> 1;
        int64 res = 0;
        if (l <= mid) res = (res + query(lc(idx), l, r)) % modulus;
        if (r > mid) res = (res + query(rc(idx), l, r)) % modulus;
        return res;
    }
    
public:
    void initialize(int size, int64 mod, const vector<int64>& arr) {
        n = size;
        modulus = mod;
        tree.resize(4 * n + 5);
        build(1, 1, n, arr);
    }
    
    void multiply(int l, int r, int64 val) {
        updateMul(1, l, r, val);
    }
    
    void add(int l, int r, int64 val) {
        updateAdd(1, l, r, val);
    }
    
    int64 queryRange(int l, int r) {
        return query(1, l, r);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    int64 mod;
    cin >> n >> q >> mod;
    
    vector<int64> data(n + 1);
    for (int i = 1; i <= n; i++) cin >> data[i];
    
    AdvancedSegmentTree ast;
    ast.initialize(n, mod, data);
    
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, y;
            int64 k;
            cin >> x >> y >> k;
            ast.multiply(x, y, k);
        } else if (op == 2) {
            int x, y;
            int64 k;
            cin >> x >> y >> k;
            ast.add(x, y, k);
        } else {
            int x, y;
            cin >> x >> y;
            cout << ast.queryRange(x, y) << '\n';
        }
    }
    
    return 0;
}

Maintaining Range Maximum with Lazy Propagation

This variant maintains range maximum values enstead of sums, useful for problems involving height constraints or capacity limits.

#include <bits/stdc++.h>
using namespace std;

struct MaxNode {
    int l, r;
    int maximum;
    int lazy;
};

class MaxSegmentTree {
private:
    vector<MaxNode> tree;
    
    int leftChild(int idx) { return idx << 1; }
    int rightChild(int idx) { return idx << 1 | 1; }
    
    void pushUp(int idx) {
        tree[idx].maximum = max(tree[leftChild(idx)].maximum, 
                               tree[rightChild(idx)].maximum);
    }
    
    void pushDown(int idx) {
        if (tree[idx].lazy != 0) {
            tree[leftChild(idx)].maximum -= tree[idx].lazy;
            tree[rightChild(idx)].maximum -= tree[idx].lazy;
            tree[leftChild(idx)].lazy += tree[idx].lazy;
            tree[rightChild(idx)].lazy += tree[idx].lazy;
            tree[idx].lazy = 0;
        }
    }
    
    void build(int idx, int l, int r, const vector<int>& arr) {
        tree[idx].l = l;
        tree[idx].r = r;
        tree[idx].lazy = 0;
        
        if (l == r) {
            tree[idx].maximum = arr[l];
            return;
        }
        
        int mid = (l + r) >> 1;
        build(leftChild(idx), l, mid, arr);
        build(rightChild(idx), mid + 1, r, arr);
        pushUp(idx);
    }
    
    void rangeDec(int idx, int l, int r, int value) {
        if (l <= tree[idx].l && tree[idx].r <= r) {
            tree[idx].maximum -= value;
            tree[idx].lazy += value;
            return;
        }
        
        pushDown(idx);
        int mid = (tree[idx].l + tree[idx].r) >> 1;
        if (l <= mid) rangeDec(leftChild(idx), l, r, value);
        if (r > mid) rangeDec(rightChild(idx), l, r, value);
        pushUp(idx);
    }
    
    int rangeMin(int idx, int l, int r) {
        if (l <= tree[idx].l && tree[idx].r <= r) {
            return tree[idx].maximum;
        }
        pushDown(idx);
        int mid = (tree[idx].l + tree[idx].r) >> 1;
        int result = INT_MAX;
        if (l <= mid) result = min(result, rangeMin(leftChild(idx), l, r));
        if (r > mid) result = min(result, rangeMin(rightChild(idx), l, r));
        return result;
    }
    
public:
    void buildTree(int size, const vector<int>& arr) {
        tree.resize(4 * size + 5);
        build(1, 1, size, arr);
    }
    
    bool decrement(int l, int r, int value) {
        if (rangeMin(1, l, r) >= value) {
            rangeDec(1, l, r, value);
            return true;
        }
        return false;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    vector<int> arr(n + 1);
    for (int i = 1; i <= n; i++) cin >> arr[i];
    
    MaxSegmentTree mst;
    mst.buildTree(n, arr);
    
    for (int i = 1; i <= m; i++) {
        int need, l, r;
        cin >> need >> l >> r;
        if (!mst.decrement(l, r, need)) {
            cout << -1 << '\n' << i;
            return 0;
        }
    }
    cout << 0;
    return 0;
}

Segment Tree for Maximum Subarray Sum

This implementation maintains maximum subarray sum using a merge function that combines prefix, sufffix, and maximum values.

#include <bits/stdc++.h>
using namespace std;

struct SubarrayNode {
    int l, r;
    int64 prefix;
    int64 suffix;
    int64 maximum;
    int64 total;
};

class MaxSubarrayTree {
private:
    vector<SubarrayNode> tree;
    
    int leftChild(int idx) { return idx << 1; }
    int rightChild(int idx) { return idx << 1 | 1; }
    
    SubarrayNode mergeNodes(const SubarrayNode& left, const SubarrayNode& right) {
        SubarrayNode result;
        result.l = left.l;
        result.r = right.r;
        result.total = left.total + right.total;
        
        result.prefix = max(left.prefix, left.total + right.prefix);
        result.suffix = max(right.suffix, right.total + left.suffix);
        result.maximum = max({left.maximum, right.maximum, left.suffix + right.prefix});
        
        return result;
    }
    
    void build(int idx, int l, int r, const vector<int64>& arr) {
        tree[idx].l = l;
        tree[idx].r = r;
        
        if (l == r) {
            tree[idx].prefix = tree[idx].suffix = tree[idx].maximum = tree[idx].total = arr[l];
            return;
        }
        
        int mid = (l + r) >> 1;
        build(leftChild(idx), l, mid, arr);
        build(rightChild(idx), mid + 1, r, arr);
        tree[idx] = mergeNodes(tree[leftChild(idx)], tree[rightChild(idx)]);
    }
    
    void pointUpdate(int idx, int pos, int64 value) {
        if (tree[idx].l == tree[idx].r) {
            tree[idx].prefix = tree[idx].suffix = tree[idx].maximum = tree[idx].total = value;
            return;
        }
        
        int mid = (tree[idx].l + tree[idx].r) >> 1;
        if (pos <= mid) pointUpdate(leftChild(idx), pos, value);
        else pointUpdate(rightChild(idx), pos, value);
        
        tree[idx] = mergeNodes(tree[leftChild(idx)], tree[rightChild(idx)]);
    }
    
    SubarrayNode query(int idx, int l, int r) {
        if (l <= tree[idx].l && tree[idx].r <= r) {
            return tree[idx];
        }
        
        int mid = (tree[idx].l + tree[idx].r) >> 1;
        if (r <= mid) return query(leftChild(idx), l, r);
        if (l > mid) return query(rightChild(idx), l, r);
        
        SubarrayNode leftResult = query(leftChild(idx), l, r);
        SubarrayNode rightResult = query(rightChild(idx), l, r);
        return mergeNodes(leftResult, rightResult);
    }
    
public:
    void initialize(int size, const vector<int64>& arr) {
        tree.resize(4 * size + 5);
        build(1, 1, size, arr);
    }
    
    void update(int position, int64 value) {
        pointUpdate(1, position, value);
    }
    
    int64 getMaxSubarraySum(int l, int r) {
        return query(1, l, r).maximum;
    }
};

Segment Tree for Binary String Operations

This specialized segment tree handles binary strings with range flip operations while maintaining longest consecutive sequences of 0s and 1s.

#include <bits/stdc++.h>
using namespace std;

struct BinaryNode {
    int l, r;
    int leftZero, leftOne;
    int rightZero, rightOne;
    int maxZero, maxOne;
    int flipTag;
};

class BinaryStringTree {
private:
    vector<BinaryNode> tree;
    string data;
    
    int lc(int idx) { return idx << 1; }
    int rc(int idx) { return idx << 1 | 1; }
    
    BinaryNode merge(const BinaryNode& a, const BinaryNode& b) {
        BinaryNode res;
        res.l = a.l;
        res.r = b.r;
        res.flipTag = 0;
        
        res.maxZero = max({a.maxZero, b.maxZero, a.rightZero + b.leftZero});
        res.maxOne = max({a.maxOne, b.maxOne, a.rightOne + b.leftOne});
        
        int leftLen = a.r - a.l + 1;
        res.leftZero = (a.leftZero == leftLen) ? leftLen + b.leftZero : a.leftZero;
        res.leftOne = (a.leftOne == leftLen) ? leftLen + b.leftOne : a.leftOne;
        
        int rightLen = b.r - b.l + 1;
        res.rightZero = (b.rightZero == rightLen) ? rightLen + a.rightZero : b.rightZero;
        res.rightOne = (b.rightOne == rightLen) ? rightLen + a.rightOne : b.rightOne;
        
        return res;
    }
    
    void applyFlip(int idx) {
        swap(tree[idx].leftZero, tree[idx].leftOne);
        swap(tree[idx].rightZero, tree[idx].rightOne);
        swap(tree[idx].maxZero, tree[idx].maxOne);
        tree[idx].flipTag ^= 1;
    }
    
    void pushDown(int idx) {
        if (tree[idx].flipTag & 1) {
            applyFlip(lc(idx));
            applyFlip(rc(idx));
            tree[idx].flipTag = 0;
        }
    }
    
    void build(int idx, int l, int r) {
        tree[idx].l = l;
        tree[idx].r = r;
        tree[idx].flipTag = 0;
        
        if (l == r) {
            if (data[l - 1] == '0') {
                tree[idx].leftZero = tree[idx].rightZero = tree[idx].maxZero = 1;
                tree[idx].leftOne = tree[idx].rightOne = tree[idx].maxOne = 0;
            } else {
                tree[idx].leftOne = tree[idx].rightOne = tree[idx].maxOne = 1;
                tree[idx].leftZero = tree[idx].rightZero = tree[idx].maxZero = 0;
            }
            return;
        }
        
        int mid = (l + r) >> 1;
        build(lc(idx), l, mid);
        build(rc(idx), mid + 1, r);
        tree[idx] = merge(tree[lc(idx)], tree[rc(idx)]);
    }
    
    void rangeFlip(int idx, int l, int r) {
        if (l <= tree[idx].l && tree[idx].r <= r) {
            applyFlip(idx);
            return;
        }
        pushDown(idx);
        int mid = (tree[idx].l + tree[idx].r) >> 1;
        if (l <= mid) rangeFlip(lc(idx), l, r);
        if (r > mid) rangeFlip(rc(idx), l, r);
        tree[idx] = merge(tree[lc(idx)], tree[rc(idx)]);
    }
    
    BinaryNode query(int idx, int l, int r) {
        if (l <= tree[idx].l && tree[idx].r <= r) {
            return tree[idx];
        }
        pushDown(idx);
        int mid = (tree[idx].l + tree[idx].r) >> 1;
        if (r <= mid) return query(lc(idx), l, r);
        if (l > mid) return query(rc(idx), l, r);
        return merge(query(lc(idx), l, r), query(rc(idx), l, r));
    }
    
public:
    void initialize(const string& s) {
        data = s;
        tree.resize(4 * s.length() + 5);
        build(1, 1, s.length());
    }
    
    void flip(int l, int r) {
        rangeFlip(1, l, r);
    }
    
    int queryMaxOnes(int l, int r) {
        return query(1, l, r).maxOne;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    
    BinaryStringTree bst;
    bst.initialize(s);
    
    while (q--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            bst.flip(l, r);
        } else {
            cout << bst.queryMaxOnes(l, r) << '\n';
        }
    }
    
    return 0;
}

Segment Tree with Binary Indexed Tree Hybrid

For problems requiring offline query processing, a combination of segment tree operations with sorting by right boundary provides efficient solutions.

#include <bits/stdc++.h>
using namespace std;

struct Query {
    int left, right;
    int index;
    
    bool operator<(const Query& other) const {
        return right < other.right;
    }
};

class OfflineQuerySolver {
private:
    static const int MAXVAL = 1000006;
    vector<int> bit;
    vector<int> lastPos;
    vector<int> answer;
    int n;
    
    int lowBit(int x) { return x & (-x); }
    
    void bitUpdate(int pos, int delta) {
        for (int i = pos; i <= n; i += lowBit(i)) {
            bit[i] += delta;
        }
    }
    
    int bitQuery(int pos) {
        int sum = 0;
        for (int i = pos; i > 0; i -= lowBit(i)) {
            sum += bit[i];
        }
        return sum;
    }
    
public:
    void solve(const vector<int>& arr, const vector<Query>& queries) {
        n = arr.size() - 1;
        bit.assign(n + 2, 0);
        lastPos.assign(MAXVAL, 0);
        answer.resize(queries.size() + 1);
        
        vector<Query> sortedQueries = queries;
        sort(sortedQueries.begin(), sortedQueries.end());
        
        int queryIdx = 0;
        for (int i = 1; i <= n; i++) {
            int val = arr[i];
            
            if (lastPos[val] != 0) {
                bitUpdate(lastPos[val], -1);
            }
            bitUpdate(i, 1);
            lastPos[val] = i;
            
            while (queryIdx < sortedQueries.size() && 
                   sortedQueries[queryIdx].right == i) {
                int l = sortedQueries[queryIdx].left;
                int r = sortedQueries[queryIdx].right;
                answer[sortedQueries[queryIdx].index] = 
                    bitQuery(r) - bitQuery(l - 1);
                queryIdx++;
            }
        }
    }
    
    int getAnswer(int idx) const {
        return answer[idx];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> arr(n + 1);
    for (int i = 1; i <= n; i++) cin >> arr[i];
    
    int m;
    cin >> m;
    vector<Query> queries(m);
    for (int i = 0; i < m; i++) {
        cin >> queries[i].left >> queries[i].right;
        queries[i].index = i;
    }
    
    OfflineQuerySolver solver;
    solver.solve(arr, queries);
    
    for (int i = 0; i < m; i++) {
        cout << solver.getAnswer(i) << '\n';
    }
    
    return 0;
}

Segment Tree for Prefix Sum Queries

For range maximum subarray sum queries, maintaining prefix sums with segment tree provides an elegant solution.

#include <bits/stdc++.h>
using namespace std;

struct PrefixNode {
    int l, r;
    long long prefixMin;
    long long prefixMax;
};

class PrefixSegTree {
private:
    vector<PrefixNode> tree;
    vector<long long> prefix;
    
    int lc(int idx) { return idx << 1; }
    int rc(int idx) { return idx << 1 | 1; }
    
    void pushUp(int idx) {
        tree[idx].prefixMin = min(tree[lc(idx)].prefixMin, 
                                  tree[rc(idx)].prefixMin);
        tree[idx].prefixMax = max(tree[lc(idx)].prefixMax, 
                                  tree[rc(idx)].prefixMax);
    }
    
    void build(int idx, int l, int r) {
        tree[idx].l = l;
        tree[idx].r = r;
        
        if (l == r) {
            tree[idx].prefixMin = prefix[l];
            tree[idx].prefixMax = prefix[l];
            return;
        }
        
        int mid = (l + r) >> 1;
        build(lc(idx), l, mid);
        build(rc(idx), mid + 1, r);
        pushUp(idx);
    }
    
    long long queryMin(int idx, int l, int r) {
        if (l <= tree[idx].l && tree[idx].r <= r) {
            return tree[idx].prefixMin;
        }
        
        int mid = (tree[idx].l + tree[idx].r) >> 1;
        long long result = LLONG_MAX;
        if (l <= mid) result = min(result, queryMin(lc(idx), l, r));
        if (r > mid) result = min(result, queryMin(rc(idx), l, r));
        return result;
    }
    
    long long queryMax(int idx, int l, int r) {
        if (l <= tree[idx].l && tree[idx].r <= r) {
            return tree[idx].prefixMax;
        }
        
        int mid = (tree[idx].l + tree[idx].r) >> 1;
        long long result = LLONG_MIN;
        if (l <= mid) result = max(result, queryMax(lc(idx), l, r));
        if (r > mid) result = max(result, queryMax(rc(idx), l, r));
        return result;
    }
    
public:
    void buildFromArray(const vector<long long>& arr) {
        int n = arr.size() - 1;
        prefix.resize(n + 1);
        prefix[0] = 0;
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + arr[i];
        }
        
        tree.resize(4 * n + 5);
        build(1, 0, n);
    }
    
    long long queryRangeMax(int l, int r) {
        return queryMax(1, l, r);
    }
    
    long long queryRangeMin(int l, int r) {
        return queryMin(1, l, r);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    
    vector<long long> arr(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    
    PrefixSegTree pst;
    pst.buildFromArray(arr);
    
    while (q--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        long long result = pst.queryRangeMax(c, d) - 
                          pst.queryRangeMin(a - 1, b - 1);
        cout << result << '\n';
    }
    
    return 0;
}

Segment Tree for Monotonic Sequence Detection

This implementation maintains sequence state including whether sequences are strictly increasing, strictly decreasing, or unimodal.

#include <bits/stdc++.h>
using namespace std;

enum SequenceState {
    SINGLE = 0,
    EQUAL = 1,
    STRICT_INC = 2,
    STRICT_DEC = 3,
    UNIMODAL = 4,
    IRREGULAR = 5
};

struct MonotoneNode {
    int l, r;
    int leftVal, rightVal;
    SequenceState state;
    int addTag;
};

class MonotoneSegTree {
private:
    vector<MonotoneNode> tree;
    vector<int> arr;
    
    int lc(int idx) { return idx << 1; }
    int rc(int idx) { return idx << 1 | 1; }
    
    MonotoneNode combine(const MonotoneNode& left, const MonotoneNode& right) {
        MonotoneNode res;
        res.l = left.l;
        res.r = right.r;
        res.leftVal = left.leftVal;
        res.rightVal = right.rightVal;
        res.addTag = 0;
        res.state = IRREGULAR;
        
        if (left.state == IRREGULAR || right.state == IRREGULAR) {
            res.state = IRREGULAR;
        } else if (left.state == SINGLE && right.state == SINGLE) {
            if (left.rightVal > right.rightVal) res.state = STRICT_DEC;
            else if (left.rightVal == right.rightVal) res.state = EQUAL;
            else res.state = STRICT_INC;
        } else if (left.state == SINGLE) {
            if (right.state == EQUAL) {
                res.state = (left.rightVal == right.rightVal) ? EQUAL : IRREGULAR;
            } else if (right.state == STRICT_INC) {
                res.state = (left.rightVal < right.leftVal) ? STRICT_INC : IRREGULAR;
            } else if (right.state == STRICT_DEC) {
                if (left.rightVal == right.leftVal) res.state = IRREGULAR;
                else if (left.rightVal > right.leftVal) res.state = STRICT_DEC;
                else res.state = UNIMODAL;
            } else if (right.state == UNIMODAL) {
                res.state = (left.rightVal < right.leftVal) ? UNIMODAL : IRREGULAR;
            }
        } else if (right.state == SINGLE) {
            if (left.state == EQUAL) {
                res.state = (right.leftVal == left.rightVal) ? EQUAL : IRREGULAR;
            } else if (left.state == STRICT_INC) {
                res.state = (right.leftVal == left.rightVal) ? IRREGULAR : 
                            (right.leftVal > left.rightVal) ? STRICT_INC : UNIMODAL;
            } else if (left.state == STRICT_DEC) {
                res.state = (right.leftVal < left.rightVal) ? STRICT_DEC : IRREGULAR;
            } else if (left.state == UNIMODAL) {
                res.state = (right.leftVal < left.rightVal) ? UNIMODAL : IRREGULAR;
            }
        } else {
            if (left.state == EQUAL || right.state == EQUAL) {
                res.state = IRREGULAR;
            } else if (left.state == STRICT_INC) {
                if (right.state == STRICT_INC) {
                    res.state = (left.rightVal < right.leftVal) ? STRICT_INC : IRREGULAR;
                } else if (right.state == STRICT_DEC) {
                    res.state = (left.rightVal != right.leftVal) ? UNIMODAL : IRREGULAR;
                } else {
                    res.state = (left.rightVal < right.leftVal) ? UNIMODAL : IRREGULAR;
                }
            } else if (left.state == STRICT_DEC) {
                if (right.state == STRICT_DEC) {
                    res.state = (left.rightVal > right.leftVal) ? STRICT_DEC : IRREGULAR;
                } else if (right.state == UNIMODAL) {
                    res.state = IRREGULAR;
                } else {
                    res.state = (left.rightVal > right.leftVal) ? UNIMODAL : IRREGULAR;
                }
            } else if (left.state == UNIMODAL) {
                if (right.state == STRICT_DEC || right.state == UNIMODAL) {
                    res.state = IRREGULAR;
                } else {
                    res.state = (left.rightVal > right.leftVal) ? UNIMODAL : IRREGULAR;
                }
            }
        }
        
        return res;
    }
    
    void pushDown(int idx) {
        if (tree[idx].addTag != 0) {
            int tag = tree[idx].addTag;
            tree[lc(idx)].leftVal += tag;
            tree[lc(idx)].rightVal += tag;
            tree[lc(idx)].addTag += tag;
            tree[rc(idx)].leftVal += tag;
            tree[rc(idx)].rightVal += tag;
            tree[rc(idx)].addTag += tag;
            tree[idx].addTag = 0;
        }
    }
    
    void build(int idx, int l, int r) {
        tree[idx].l = l;
        tree[idx].r = r;
        tree[idx].addTag = 0;
        
        if (l == r) {
            tree[idx].leftVal = tree[idx].rightVal = arr[l];
            tree[idx].state = SINGLE;
            return;
        }
        
        int mid = (l + r) >> 1;
        build(lc(idx), l, mid);
        build(rc(idx), mid + 1, r);
        tree[idx] = combine(tree[lc(idx)], tree[rc(idx)]);
    }
    
    void rangeAdd(int idx, int l, int r, int value) {
        if (l <= tree[idx].l && tree[idx].r <= r) {
            tree[idx].leftVal += value;
            tree[idx].rightVal += value;
            tree[idx].addTag += value;
            return;
        }
        
        pushDown(idx);
        int mid = (tree[idx].l + tree[idx].r) >> 1;
        if (l <= mid) rangeAdd(lc(idx), l, r, value);
        if (r > mid) rangeAdd(rc(idx), l, r, value);
        tree[idx] = combine(tree[lc(idx)], tree[rc(idx)]);
    }
    
    MonotoneNode query(int idx, int l, int r) {
        if (l <= tree[idx].l && tree[idx].r <= r) {
            return tree[idx];
        }
        
        pushDown(idx);
        int mid = (tree[idx].l + tree[idx].r) >> 1;
        if (r <= mid) return query(lc(idx), l, r);
        if (l > mid) return query(rc(idx), l, r);
        return combine(query(lc(idx), l, r), query(rc(idx), l, r));
    }
    
public:
    void initialize(const vector<int>& input) {
        arr = input;
        int n = arr.size() - 1;
        tree.resize(4 * n + 5);
        build(1, 1, n);
    }
    
    void add(int l, int r, int value) {
        rangeAdd(1, l, r, value);
    }
    
    bool isSingleOrEqual(int l, int r) {
        MonotoneNode result = query(1, l, r);
        return result.state == SINGLE || result.state == EQUAL;
    }
    
    bool isSingleOrIncreasing(int l, int r) {
        MonotoneNode result = query(1, l, r);
        return result.state == SINGLE || result.state == STRICT_INC;
    }
    
    bool isSingleOrDecreasing(int l, int r) {
        MonotoneNode result = query(1, l, r);
        return result.state == SINGLE || result.state == STRICT_DEC;
    }
    
    bool isUnimodal(int l, int r) {
        MonotoneNode result = query(1, l, r);
        return result.state == UNIMODAL;
    }
};