线段树

字数

1513 字

阅读时间

7 分钟

---

一、原理

1. push up操作：由子节点去计算父节点的信息
2. push down操作（也称为懒标记、延迟标记）：把当前父节点的修改信息下传给子节点
3. 扫描线

线段树结构：

线段树除了最后一层外，是个满二叉树，可以用一维数组存整棵树 🌟🌟🌟若编号为 x 的节点，其父节点为 $x>>1$ （下取整），左儿子为 $2x(\mathrm{或}：x<<1)$ ，右儿子为 $2x+1(x<<1|1)$ （x 左移 1 或 1）

开数组时需要开 4n - 1 的空间

只有涉及区间修改的，才会用到懒标记，即：pushdown

二、代码功能实现

基本操作

1. pushup（u）
2. build（）：将一段区间初始化为线段树
3. modify（）：
   1. 修改单点
   2. 修改区间（pushdown） ----- 用到懒标记
4. query（）：查询某段区间的信息
5. 线段树是动态维护的

build 操作

递归建树build：O(n)

void build(int u, int l, int r)
{
	tr[u] = {l, r};// 当前节点的左右儿子
	if (l == r) return ;// 如果已经是叶子结点了，就不再递归
	int mid = tr[u].l + tr[u].r >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);// 递归建立左右区间
	pushup(u); // 更新父节点
}

lazy标记

适用于区间修改操作

优化前：
	单点更新：O(log⁡n)
	区间更新：O(nlog⁡n)
	区间查询：O(log⁡n)
优化后：
	单点更新：O(log⁡n)
	区间更新：O(log⁡n)
	区间查询：O(log⁡n)

// 假定目前的题目场景为，求指定区间范围内的元素总和
struct Node
{
	int l, r, sum, add; // l,r分别表示区间左右端点;sum 表示区间总和,add表示懒标记，即：区间修改的值
}tr[N * 4];

void pushup(int u) // 往上传，由子节点更新父节点
{
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u) // 区间修改，懒标记下传
{
	if (tr[u].add) // 如果存在懒标记，则下传
	{
		tr[u << 1].sum += tr[u].add * (tr[u << 1].r - tr[u << 1].l + 1);
		tr[u << 1 | 1].sum += tr[u].add * (tr[u << 1 | 1].r - tr[u << 1 | 1].l +1);
		tr[u << 1].add += tr[u].add;
		tr[u << 1 | 1].add += tr[u].add;
		tr[u].add = 0;
	}
}

// query 和 update 操作都需要用到 pushdown
void update(int u, int l, int r, int x)
{
	if (tr[u].l >= l && tr[u].r <= r)
	{
		tr[u].sum += (tr[u].r - tr[u].l + 1) * x;
		tr[u].add += x;
		return ;
	}
	int mid = tr[u].l + tr[u].r >> 1;
	pushdown(u); // 更新子节点前，先下传懒标记
	if (l <= mid) update(u << 1, l, r, x);
	if (r > mid) update(u << 1 | 1, l, r, x);
	pushup(u); // 更新父节点
}

int query(int u, int l, int r)
{
	if (tr[u].l >= l && tr[u].r <= r) 
		return tr[u].sum;
	int sum = 0;
	int mid = tr[u].l + tr[u].r >> 1;
	pushdown(u); // 遍历子节点之前先下传懒标记
	if (l <= mid) sum += query(u << 1, l, r);
	if (r > mid) sum += query(u << 1 | 1, l, r);
	return sum;
}

三、适用场景

不同于树状数组仅适用于单点修改，区间查询，线段树算法不仅可实现单点修改，还可实现区间修改，可用于求区间内极值、最值等情况

四、例题

// 求区间的最大连续子段和，涉及单点修改
// 因为要求区间内的最大连续子段和，所以要考虑该最大子段所在位置，判断其在左区间、右区间，亦或是横跨左右区间，所以不仅需要记录线段树区间的最大子段和
//还要记录左区间的最大后缀和与右区间的最大前缀和，这两者在其父节点区间处是连续的，所以需要判断前缀和与后缀和的和是否比左右区间内的最大前缀和大
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 500010;

int n, m;
int w[N];
struct Node
{
    int l, r;
    int sum, lmax, rmax, tmax; // 区间总和（因为要考虑左区间 + 右区间最大前缀和，可能比左区间最大后缀和 + 右区间最大前缀和 更大），最大后缀和（左区间），最大前缀和（右区间）和区间内最大连续子段和
}tr[N * 4];

void pushup(Node &u, Node &l, Node &r) // u 表示 l 和 r 的父节点，l 表示左儿子，r 表示右儿子
{
    u.sum = l.sum + r.sum;
    u.lmax = max(l.lmax, l.sum + r.lmax);
    u.rmax = max(r.rmax, l.rmax + r.sum);
    u.tmax = max(l.rmax + r.lmax, max(l.tmax, r.tmax));
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, w[r], w[r], w[r], w[r]};  // 最大子段和至少包含一个数，所以存为 w[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 modify(int u, int x, int v)
{
    if (tr[u].l == x && tr[u].r == x) tr[u] = {x, x, v, v, v, v}; // 找到该单点，修改值
    else 
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

Node query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u];
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid) return query(u << 1, l, r); // 如果区间[l, r]在左儿子区间，则往左找
        else if (l > mid) return query(u << 1 | 1, l, r); // 如果区间[l, r] 在右儿子区间，则往右找
        else // 如果是横跨左右儿子区间
        {
            Node left = query(u << 1, l, r); // 找到左儿子部分, 因为 r > mid，所以左儿子部分一定满足 tr[u].r <= r
            Node right = query(u << 1 | 1, l, r); // 找到右儿子部分，同样的，因为 l <= mid, 右儿子部分一定满足 tr[u].l >= l
            // 故也可写作：left = query(u << 1, l, mid), right = query(u << 1 | 1, mid + 1, r);
            Node res;
            pushup(res, left, right); // 用子节点更新父节点，找出最大子段和
            return res;
        }

    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> w[i];

    build(1, 1, n);

    while(m --)
    {
        int k, x, y;
        cin >> k >> x >> y;
        if (k == 2)
        {
            modify(1, x, y);
        }
        else if (k == 1)
        {
            if (x > y) swap(x, y);
            cout << query(1, x, y).tmax << endl;
        }
    }

    return 0;
}

贡献者

freeway348

文件历史

最后编辑于 4 天前查看完整历史

e587f-Update 简介梗概.md