动态开点线段树原理

例题 1

统计区间中的整数数目

#define ls(x) tr[x].L
#define rs(x) tr[x].R
class CountIntervals {
    static const int N = 8e5 + 5;
    struct node{
        int l, r, cnt = 0;
        int L = -1, R = -1;
    }tr[N];
    int idx = 1;
    void push_up(int u) {
        tr[u].cnt = 0;
        if (ls(u) != -1) {
            tr[u].cnt += tr[ls(u)].cnt;
        }
        if (rs(u) != -1) {
            tr[u].cnt += tr[rs(u)].cnt;
        }
    }
    void add2(int u, int l, int r) {
        if (tr[u].l == tr[u].r) {
            tr[u].cnt = 1;
            return;
        }
        if (l <= tr[u].l && r >= tr[u].r) {
            tr[u].cnt = tr[u].r - tr[u].l + 1;
            return;
        }
        if (tr[u].cnt == tr[u].r - tr[u].l + 1) return;
        int mid = (tr[u].l + tr[u].r) >> 1;

        if (l <= mid) {
            int& L = ls(u);
            if (L == -1) {
                L = idx ++;
                tr[L] = {tr[u].l, mid};
            }
            add2(L, l, r);
        }
        if (r > mid) {
            int& R = rs(u);
            if (R == -1) {
                R = idx ++;
                tr[R] = {mid + 1, tr[u].r};
            }
            add2(R, l, r);
        }
        push_up(u);
    }

public:
    CountIntervals() {
        tr[idx ++] = {1, 1000000005, 0};
    }

    void add(int left, int right) {
        add2(1, left, right);
        // cout << idx << endl;
    }

    int count() {
        // cout << idx << endl;
        return tr[1].cnt;
    }
};

/**
 * Your CountIntervals object will be instantiated and called as such:
 * CountIntervals* obj = new CountIntervals();
 * obj->add(left,right);
 * int param_2 = obj->count();
 */

例题 2

Range 模块

#define ls(u) tr[u].L
#define rs(u) tr[u].R
class RangeModule {
    static const int N = 1E6;
    struct node{
        int l, r;
        int L, R;
        int sum = 0;
        int f = 0;
    }tr[4 * N];
    int idx = 1;
    void push_up(int u) {
        tr[u].sum = tr[ls(u)].sum + tr[rs(u)].sum;
    }
    void push_dowm(int u) {
        int& L = ls(u), &R = rs(u);
        if (!L) {
            L = ++ idx;
            tr[L] = {tr[u].l, tr[u].l + tr[u].r >> 1};
        }
        if (!R) {
            R = ++ idx;
            tr[R] = {(tr[u].l + tr[u].r >> 1) + 1, tr[u].r};
        }

        if (tr[u].f == 0) return;
        else if (tr[u].f == -1) {
            tr[L].sum = 0;
            tr[R].sum = 0;
        }else {
            int len = tr[u].r - tr[u].l + 1;
            tr[L].sum = len - len / 2;
            tr[R].sum = len / 2;
        }
        tr[L].f = tr[u].f;
        tr[R].f = tr[u].f;
        tr[u].f = 0;
    }
    void update(int u, int l, int r, int f) {
        if (l <= tr[u].l && tr[u].r <= r) {
            tr[u].f = f;
            if (f == 1)
                tr[u].sum = tr[u].r - tr[u].l + 1;
            else tr[u].sum = 0;
            return;
        }
        int mid = tr[u].r + tr[u].l >> 1;
        push_dowm(u);
        if (l <= mid) update(ls(u), l, r, f);
        if (r > mid) update(rs(u), l, r, f);
        push_up(u);
    }
    int query(int u, int l, int r) {
        if (l <= tr[u].l && tr[u].r <= r) {
            return tr[u].sum;
        }
        int mid = tr[u].l + tr[u].r >> 1;
        push_dowm(u);
        int ret = 0;
        if (l <= mid) ret += query(ls(u), l, r);
        if (r > mid) ret += query(rs(u), l, r);
        return ret;
    }
public:
    RangeModule() {
        tr[1] = {1, 1000000005};
    }

    void addRange(int left, int right) {
        update(1, left, right - 1, 1);
    }

    bool queryRange(int left, int right) {
        // if (left == 13 && right == 15) cout << query(1, 13, 14) << endl;
        return query(1, left, right - 1) == (right - left);
    }

    void removeRange(int left, int right) {
        update(1, left, right - 1, -1);
    }
};

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule* obj = new RangeModule();
 * obj->addRange(left,right);
 * bool param_2 = obj->queryRange(left,right);
 * obj->removeRange(left,right);
 */