高级数据结构

线段树

1、单点修改线段树

满二叉树 -> 一维数组存储整棵树

对于编号\(x\)的节点：

• 父节点：\(\lfloor \frac{x}{2} \rfloor\) x >> 1
• 左儿子：\(2x\) x << 1
• 右儿子：\(2x+1\) x << 1 | 1

节点个数（线段树的空间）：\(4n\)

时间复杂度：\(O(logn)\)

线段树的操作：

线段树的样式：

对于不同区间的操作：

struct Node {
    int l, r;
    int v;    // 需要维护的信息和懒标记
} tr[N * 4];

// 由子节点的值计算父节点
void pushup(int u) {
    // 利用左右儿子信息维护当前节点的信息
    tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}

void build(int u, int l, int r) {
    if (l == r) tr[u] = {l, r};
    else {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);        // 更新父节点信息
    }
}

void update(int u, int l, int r, int d) {
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].v = d;    // 修改区间
    } else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) update(u << 1, l, r, d);
        if (r > mid) update(u << 1 | 1, l, r, d);
        pushup(u);        // 更新父节点信息
    }
}

int query(int u, int l, int r) {
    // 树中节点已经包含在[l, r]中
    if (tr[u].l >= l && tr[u].r <= r) {
        return tr[u].v;
    } else {
        int mid = tr[u].l + tr[u].r >> 1;
        int res = 0;
        if (l <= mid) res = query(u << 1, l, r);
        if (r > mid) res += query(u << 1 | 1, l, r);
        return res;
    }
}

差分

2、懒标记线段树

3、扫描线法