线段树专题
注意：此文乃个人对线段树的见解，各位大佬如发现错误请批评指正
什么是线段树
线段树顾名思义，就是将一个数列的各个区间当成是树上的节点并维护。
线段树用来干什么
一般用来进行区间查改(矩阵查改本蒟蒻不会)
线段树节点如何编号
假设当前节点的编号为 \(k\)，左儿子的编号为 \(2k\)，右儿子的为 \(2k+1\)
[T1 区间加,求区间和](P3372 [模板]线段树 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
这道题我们执行两个操作
1 x y k表示将 \([x,y]\) 这个区间的所有值加上 \(k\)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 x y k将 \([x,y]\) 这个区间的所有值乘 \(k\)2 x y k将 \([x, y]\) 这个区间的所有值加 \(k\)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)
不会可以看[题解](C. [例题3]公园遛狗 - ljfyyds - 博客园 (cnblogs.com))
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]); //单点修改
}