Segment tree iterative with index

segtree_it_index.cpp

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

template <typename T>
class segment_tree {
   private:
    vector<pair<T, T>> tree; // 0-indexed
    T n;
   public:
    segment_tree(vector<T> &nums) {
        n = nums.size();
        tree = vector<pair<T, T>>(2 * n);
        for (T i = n; i < 2 * n; i++) {
            tree[i] = {nums[i - n], i - n};
        }
        for (T i = n - 1; i > 0; i--) {
            tree[i] = max(tree[2 * i], tree[2 * i + 1]); // query type
        }
    }
    void update(T pos, T val) {
        pos += n;
        tree[pos].first = val;  // edit "=" to change edit mode
        while (pos > 0) {
            T l = pos;
            T r = pos;
            if (pos % 2 == 0)
                r = pos + 1;
            else
                l = pos - 1;
            tree[pos / 2] = max(tree[l], tree[r]); // query type
            pos /= 2;
        }
    }
    T query(T l, T r) {
        l += n;
        r += n;
        pair<T, T> ans = {-1, -1};
        while (l <= r) {
            if (l % 2 == 1) {
                ans = max(ans, tree[l]);
                l++;
            }
            if (r % 2 == 0) {
                ans = max(ans, tree[r]); // query type
                r--;
            }
            l /= 2;
            r /= 2;
        }
        return ans.first; // first is value, second is index
    }
};

int main() {
    vector<ll> v = {1, 3, 2, 4};
    segment_tree<ll> tree(v);
    cout << tree.query(0, 3) << '\n';  // 4
    tree.update(0, 5);
    cout << tree.query(0, 3) << '\n';  // 5
}