线段树

2023-11-17 20:50:40

线段树

1.线段树的建树

build函数:
build(u, l, r):u表示当前节点编号，l、r分别是该节点所代表区间的左右端点[l, r].

struct SegmentTree{
    int l, r;
    int dat;
}t[SIZE * 4];

void build(int u, int L, int R)
{
    t[u].l = L, t[u].r = R;
    if (L == R) {
        t[u].dat = a[L];
        return;
    }
    int mid = (L + R) >> 1;
    build(2*u, L, mid);
    build(2*u + 1, mid + 1, R);
    //一般来说是Pushup()操作;
    t[u].dat = max(t[u*2].dat, t[u*2 + 1].dat);
}

2.线段树的单点修改

线段树中，根节点(编号为1)是执行的入口，需要从根节点出发，递归找到区间[x, x]的叶节点，然后对该节点
进行修改，并自底向上更新信息。时间复杂度为O(logN):树的高度;

//在节点编号为u,区间x位置处，变更为v;
void change(int u, int x, int v)
{
    if (t[u].l == t[u].r) {
        t[u].dat = v; return;
    }

    int mid = (t[u].l + t[u].r) >> 1;
    if (x <= mid) {
        //左子树遍历;
        change(2*u, x, v);
    } else {
        change(2*u + 1, x , v);
    }
    //自底向上更新信息;
    t[u].dat = max(t[2*u].dat, t[2*u + 1].dat);
}

3.区间查询

假设我们所想要查询的区间为[L, R], 线段树所建立的区间为[TL, TR];
那么从根节点开始，递归执行如下过程:

如果[L, R] 包含[TL, TR],说明L<=TL && R >= TR, 那么直接返回[TL, TR]上的相关信息即可, 对于非[TL, TR]区间的不用考虑，因为一开始就建立的线段树就没考虑这段区间;
如果[L, R]和[TL, TR]有部分重叠, 那么可以分三种情况讨论:
对于mid = (TL + TR) / 2, 且有TL <= L <= TR <= R,

如果L > mid, 说明[TL, TR]的右半部分和[L, R]重叠，因此只需递归右边即可;
如果 L <= mid, 虽然会递归两颗子树，但是右半边的递归会和1情况类似，所以右边递归时会直接返回;

对于L <= TL <= R <= TR, 情况和上面是对称的;
如果TL <= L <= R <=TR, 即[L, R]被[TL, TR]所包含，
- 对于L,R都处于mid的左边或右边时，那么只会递归一颗子树;
- 当L, R分别在mid的左右两边时，这时才会递归两边，但需要考虑到下一层递归时，会变成2或3中部分重叠的情况
如果[L, R]和[TL, TR]不存在重叠，因为我们是从根节点开始，即[1, N]开始，除非一开始就是没有交集的，不然必定会回到1和2的情况，因此这种情况不必讨论;

比如查询区间[l, r]上的最大值;

int Query(int u, int l, int r)
{
    if (t[u].l >= l && t[u].r <= r) {
        return t[u].dat; //完全包含关系;
    }

    int mid = (t[u].l + t[u].r) >> 1;
    int val = -(1<<30); //-inf;
    if (l <= mid) val = max(val, ask(2*u, l, r));  //左子节点有重叠;
    if (r > mid) val = max(val, ask(2*u + 1, l, r)); //右子节点有重叠;
    return val;
}

参考

算法进阶指南；