线段树专题

注意：此文乃个人对线段树的见解，各位大佬如发现错误请批评指正

什么是线段树

线段树顾名思义，就是将一个数列的各个区间当成是树上的节点并维护。

线段树用来干什么

一般用来进行区间查改(矩阵查改本蒟蒻不会)

线段树节点如何编号

假设当前节点的编号为 \(k\)，左儿子的编号为 \(2k\)，右儿子的为 \(2k+1\)

[T1 区间加,求区间和](P3372 [模板]线段树 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

这道题我们执行两个操作

1. 1 x y k 表示将 \([x,y]\) 这个区间的所有值加上 \(k\)
2. 2 x y 表示求 \([x,y]\) 内每个数的和

先考虑线段树中要维护什么

struct node
{
    int l, r;//当前区间的左端点和右端点
    int sum, add;//当前区间的区间和和加法懒标记
}tr[4 * N];

上传答案

\(\text{update}:\)就是我们已经把左儿子(左区间)和右儿子(右区间)都做好了去更新

void update(int p)
{
    tr[p].sum = tr[ls].sum + tr[rs].sum;//当前区间和为左区间的和+右区间的和
}

\(\text{ls}\) 表示做儿子编号，即为\(2k\)，\(\text{rs}\) 同理

\(\text{build}:\) 首先，根节点所代表的区间为 \([1,n]\) ，我们在这里进入函数，然后先记录线段树节点的基本信息，然后建立左右子树，这里注意如果递归到叶子节点要回溯，最后上传。

void build(int p, int l, int r)
//p表示当前递归到的节点编号，l表示当前节点区间所对应的左端点，r表示当前区间所对应的右端点
{
    tr[p] = {l, r, a[l], 0};
    if(l == r)
        return;
   	int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(p);
}

\(\text{pushdown}:\) 下传懒标记，就是将上面大区间更改的值，下传到小区间进行修改

这个直接看代码和注释理解吧

void pushdown(int p)
//p表示当前节点的编号
{
    int l = tr[p].l, r = tr[p].r, a = tr[p].add;
    int mid = (l + r) >> 1;//算中间值
    tr[ls].sum += (mid - l + 1) * a;//左区间[l,mid]的长度乘上每个数加的值
    tr[rs].sum += (r - mid) * a;//右区间[mid + 1, r]的长度乘上每个数加的值
    tr[ls].add += a;//懒标记下传，后面给儿子的儿子操作
    tr[rs].add += a;
    tr[p].add = 0;//当前的懒标记用完了，以后不能用
}

\(\text{update}:\) 区间加

如果完全包含在要加的区间内，就直接加，如果不包含就先下传，然后如果左儿子又包含就递归左儿子，如果右儿子有包含就递归右儿子,注意最后上传

void update(int p, int ql, int qr, int x)
//代表当前的节点，要加的区间左端点，要加的区间右端点，要加的值
{
    if(ql <= tr[p].l && tr[p].r <= qr)//完全包含
    {
        tr[p].sum += (tr[p].r - tr[p].l + 1) * x;
        tr[p].add += x;
        return;
    }
    pushdown(p);
    int mid = (tr[p].l + tr[p].r) >> 1;
    if(ql <= mid)
    	update(ls, ql, qr, x);
    if(qr > mid)
        update(rs, ql, qr, x);
   	pushup(p);
}

\(\text{query}:\) 区间查询

如果完全包含就返回当前区间的答案，否则先下传，然后如果左边又包含就加上左子树的答案，右边有包含就加上右子树的答案

int query(int p, int ql, int qr)
//代表当前的节点，查询的区间左端点，查询的区间右端点
{
	if(ql <= tr[p].l && tr[p].r <= qr)
    	return tr[p].sum;
   	int mid = (tr[p].l + tr[p].r) >> 1;
    int ans = 0;
    if(ql <= mid)
        ans += query(ls, ql, qr);
   	if(qr > mid)
        ans += query(rs, ql, qr);
   	return ans;
}

然后这道题就结束了。

T2 区间加，区间乘，求区间和

三个操作

1. 1 x y k 将 \([x,y]\) 这个区间的所有值乘 \(k\)
2. 2 x y k 将 \([x, y]\) 这个区间的所有值加 \(k\)
3. 3 x y 求 \([x,y]\) 区间和模 \(m\) 的结果

线段树维护的信息

struct node
{
    int l, r;
    int sum, mul, add;//区间和，乘法和加法懒标记
}tr[N];

上传答案与上面一样

\(\text{build}\) 建树

void build(int p, int l, int r)//参数定义同上
{
    tr[p] = {l, r, a[r], 1, 0};//这个地方不同，多维护了一个乘法懒标记
    if(l == r)
        return;
   	int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(p);
}

\(\text{pushdown}\) 下传懒标记

void calc(node &t, int m, int a)//单点下传答案，乘m加a
{
    t.sum = (a * (t.r - t.l + 1) + t.sum * m) % mod;
    //对于区间和，要加上的贡献分别是：加法区间长度乘加的值，乘法是区间和乘上乘的值 ’
    t.mul = (t.mul * m) % mod;
    t.add = (t.add * m + a) % mod;//注意是先乘后加
}
void pushdown(int p)
{
    //左右儿子依次下传
    calc(tr[ls], tr[p].mul, tr[p].add);
    calc(tr[rs], tr[p].mul, tr[p].add);
    tr[p].mul = 1;//后面不能用了
    tr[p].add = 0;
}

\(\text{update}\) 区间修改

void update(int p, int ql, int qr, int m, int a)//区间乘m加a
{
    if(qr < tr[p].l || tr[u].r < ql)//不包含在当前的区间里
        return;
   	if(ql <= tr[p].l && tr[p].r <= qr)//完全包含
    {
        calc(tr[p], m, a);//修改当前节点的答案
        return;
    }
    pushdown(p);
    update(ls, ql, qr, m, a);
    update(rs, ql, qr, m, a);
    pushup(p);
}

\(\text{query}\) 区间查询

void query(int p, int ql, int qr)
{
    if(qr < tr[p].l || tr[p].r < ql)//不包含
        return 0;//对答案的贡献为0
    if(ql <= tr[p].l && tr[p].r <= qr)//完全包含
    	return tr[p].sum;
    pushdown(p);
    return (query(ls, ql, qr) + query(rs, ql, qr)) % mod;//当前贡献等于左子树贡献+右子树贡献
}

ok,又AC了一题

看到这里的可以先做一个习题

[公园遛狗](C. [例题3]公园遛狗 - 「数据结构」第4章 线段树 - 算法高效进阶2023 - 课程 - YbtOJ)

T3 种地收益(线段树优化 \(\text{dp}\))

这个就上难度了

考虑 \(dp\)

状态表示 \(f_i\) 表示 \(i\) 左侧都是可以给你带来收益的地(包含 \(i\) ) 所能带来的最大收益

设 \(s_i\) 表示将前 \(i\) 个地变成不荒地的代价，\(g_i\) 表示前 \(i\) 个 \(f\) 值的最大值 $g_i=\max{f_k}(0≤k≤i) $ \(cost(i,j)\) 表示 \([i,j]\) 区间能获得的收益。

状态转移方程 \(f_i=\max\{g_j-(s_i-s_j)+cost(j+1,i)\}(0≤j<i)\)

意思就是 \(j\) 之前的最好答案减去将 \(j+1 \sim i\) 变成不是荒地的代价加上获得的收益

这个算法要枚举 \(i\) 和 \(j\) ，时间复杂度为 \(O(n^2)\) 显然过不了

首先我们发现在 \(j\) 的枚举过程中 \(s_i\) 永远都是不变的，所以原式子变为

我们用线段树维护 \(g_j + s_j + cost(j+1,i)\) 的最大值

\(g_j+s_j\) 定下来不管 \(i\) 怎么往右移动都不会变了，所以变的只有 \(cost(j+1,i)\) 这一项

什么时候 \(cost\) 值会增加

我们发现只有新添加一个新的区间时答案会增加，这个时候 \(i\) 等于某个 \(r_k\)

右端点固定是 \(i\) 那么需要修改的区间只有左端点小于 \(l_k\) ，所以我们把 \([0,l)\) 的区间加上收益 \(p_k\) 区间加

然后计算用区间查找 \(g_j+s_j\) ，最后单点修改 \(i\) 这个位置

答案为 \(g_n\)

//核心代码
 int pos = 1; //初始化为1
for (int i = 1; i <= n; i++)
{
    while (pos <= m && infor[pos].r == i)
    {
        update(1, 0, infor[pos].l - 1, infor[pos].p); //区间修改
        //[0,l-1]加上p[pos]
        pos++;
    }
    f[i] = query(1, 0, i - 1) - s[i]; //查找[0,i]之中的最大答案
    if (i == 1)
        g[i] = f[i];
    else
        g[i] = max(g[i - 1], f[i]);
    update(1, i, i, g[i] + s[i]); //单点修改
}