线段树的应用场景有哪些

作者：佚名上传时间：2023-03-16 运行软件：N/A 软件版本：N/A 版权申诉

线段树是一种二叉树数据结构，主要用于处理一维区间查询问题。它的应用场景包括但不限于以下几个方面：

区间最值查询

线段树可以用来求解区间最值查询问题，例如区间最大值、最小值、和等。以下是一段示例代码和代码释义：

const int MAXN = 1e5 + 5;
int n, m, maxn[MAXN << 2], a[MAXN];

void build(int l, int r, int rt) {
    if (l == r) {
        maxn[rt] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    maxn[rt] = max(maxn[rt << 1], maxn[rt << 1 | 1]);
}

int query(int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R) {
        return maxn[rt];
    }
    int mid = (l + r) >> 1, ans = 0;
    if (L <= mid) ans = max(ans, query(L, R, l, mid, rt << 1));
    if (R > mid) ans = max(ans, query(L, R, mid + 1, r, rt << 1 | 1));
    return ans;
}

代码释义： - build函数用于建立线段树，其中l、r、rt分别表示当前区间的左右端点和节点编号。如果当前区间只有一个元素，那么maxn[rt]就是这个元素的值；否则，将当前区间分为两个子区间，分别递归地建立左右子树，并将当前节点的值设为左右子树中的最大值。 - query函数用于查询区间最大值，其中L、R表示查询区间的左右端点，l、r、rt同上。如果当前区间被包含在查询区间中，直接返回当前节点的值；否则，将当前区间分为两个子区间，分别递归地查询左右子树，并将左右子树中的最大值取最大值后返回。

区间修改和查询

线段树还可以用来解决区间修改和查询问题，例如区间加、减、乘、除以及异或等。以下是一段示例代码和代码释义：

const int MAXN = 1e5 + 5;
int n, m, addv[MAXN << 2], sum[MAXN << 2], a[MAXN];

void build(int l, int r, int rt) {
    if (l == r) {
        sum[rt] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

void pushdown(int rt, int ln, int rn) {
    if (addv[rt]) {
        addv[rt << 1] += addv[rt];
        addv[rt << 1 | 1] += addv[rt];
        sum[rt << 1] += addv[rt] * ln;
        sum[rt << 1 | 1] += addv[rt] * rn;
        addv[rt] = 0;
    }
}

void update(int L, int R, int C, int l, int r, int rt) {
    if (L <= l && r <= R) {
        addv[rt] += C;
        sum[rt] += C * (r - l + 1);
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(rt, mid - l + 1, r - mid);
    if (L <= mid) update(L, R, C, l, mid, rt << 1);
    if (R > mid) update(L, R, C, mid + 1, r, rt << 1 | 1);
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

int query(int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R) {
        return sum[rt];
    }
    int mid = (l + r) >> 1;
    pushdown(rt, mid - l + 1, r - mid);
    int ans = 0;
    if (L <= mid) ans += query(L, R, l, mid, rt << 1);
    if (R > mid) ans += query(L, R, mid + 1, r, rt << 1 | 1);
    return ans;
}

代码释义： - build函数用于建立线段树，其中l、r、rt同上。如果当前区间只有一个元素，那么sum[rt]就是这个元素的值；否则，将当前区间分为两个子区间，分别递归地建立左右子树，并将当前节点的值设为左右子树中的元素之和。 - pushdown函数用于将当前节点的修改操作下传到左右子树中，其中rt为当前节点编号，ln、rn分别为左右子树的长度。 - update函数用于对区间进行修改，其中L、R表示修改区间的左右端点，C表示修改的值，l、r、rt同上。如果当前区间被包含在修改区间中，直接将addv[rt]和sum[rt]分别加上C和C*(r-l+1)；否则，将当前区间分为两个子区间，分别递归地修改左右子树，并更新当前节点的值。 - query函数用于查询区间和，其中L、R表示查询区间的左右端点，l、r、rt同上。如果当前区间被包含在查询区间中，直接返回当前节点的值；否则，将当前区间分为两个子区间，分别递归地查询左右子树，并将左右子树中的和相加后返回。