Дерево отрезков (реализация)

const int N = 1 << 20;

struct seg_tree {
    int t[N * 2 + 228];
    int mod[N * 2 + 228];

    seg_tree() {

    }

    void build(vector<int> a) {
        fill(t, t + N * 2, INF);
        for (int i = 0; i < a.size(); ++i) {
            t[i + N] = a[i];
        }
        for (int i = N - 1; i >= 0; --i) {
            t[i] = min(t[i * 2], t[i * 2 + 1]);
        }
    }

    void chg(int i, int v) {
        i += N;
        t[i] = v;
        while (i != 1) {
            // t[i >> 1] = t[i] + t[i ^ 1];
            i >>= 1;
            t[i] = min(t[i * 2], t[i * 2 + 1]);
        }
    }

    void push(int i, int len) {
        if (mod[i] != -1) {
            if (i < N) {
                mod[i * 2] = mod[i];
                mod[i * 2 + 1] = mod[i];
            }
            t[i] = mod[i];
            mod[i] = -1;
        }
    }

    int get(int i, int L, int R, int Ln, int Rn) {
        push(i, R - L);
        if (Ln <= L && R <= Rn) {
            return t[i];
        }
        if (Rn <= L || R <= Ln) {
            return INF;
        }
        int M = (L + R) >> 1;
        return min(get(i * 2,     L, M, Ln, Rn),
                   get(i * 2 + 1, M, R, Ln, Rn));
    }

    int find(int i, int L, int R, int Ln, int Rn, int val) {
        push(i, R - L);
        if (Rn <= L || R <= Ln || t[i] >= val) return -1;
        if (R - L == 1) return L;
        int M = (L + R) >> 1;
        int ans = find(i * 2, L, M, Ln, Rn, val);
        if (ans == -1) {
            ans = find(i * 2 + 1, M, R, Ln, Rn, val);
        }
        return ans;
    }

    void chg(int i, int L, int R, int Ln, int Rn, int d) {
        if (Ln <= L && R <= Rn) {
            mod[i] = d;
            push(i, R - L);
            return;
        }
        push(i, R - L);
        if (Rn <= L || R <= Ln) {
            return;
        }
        int M = (L + R) >> 1;
        chg(i * 2    , L, M, Ln, Rn, d);
        chg(i * 2 + 1, M, R, Ln, Rn, d);
        t[i] = min(t[i * 2], t[i * 2 + 1]);
    }
};