const int MAXN = pow(2, 17);

struct segment_tree {
    int tree[MAXN * 2];

    segment_tree() {}

    void change(int i, int d) {
        i += MAXN;
        while (i > 0) {
            tree[i] += d;
            i /= 2;
        }
    }

    int get(int i, int L, int R, int Ln, int Rn) {
        if (R <= Ln || Rn <= L) return 0;
        if (Ln <= L && R <= Rn) return tree[i];
        int M = (L + R) / 2;
        return get(i * 2, L, M, Ln, Rn) + get(i * 2 + 1, M, R, Ln, Rn);
    }
}