目录
一、线段树算法的概念
二、为什么需要线段树
三、线段树算法的实现
(1)建树
(2)查询
(3)修改
(4)综合代码,求区间和
(5)综合代码,求区间最大值
四、Lazy标记
一、线段树算法的概念
线段树(Segment Tree)是一种基于二分思想的数据结构,常常用于处理区间查询和区间修改。线段树的常用操作包括建树、查询、修改。
线段树的建树过程可以使用递归实现,也可以使用非递归实现(通常使用栈来实现)。
线段树的查询和修改基本都是从根节点开始,往下遍历到叶子节点或者与查询区间(或修改区间)不相交的节点为止。线段树相关问题经常需要使用懒惰标记(Lazy Tag)来优化。
线段树常用于以下场景:区间最值查询、区间求和、区间修改等
二、为什么需要线段树
考虑这样两个场景:
- 对于一个长度为 n 的数组,现在给定 l,r 让你求 l 到 r 所有元素的和,有多个这样的询问.
- 对于一个长度为 n 的数组,现在对数组的第 k 个元素进行修改后,给定 l,r 让你求 l 到 r 所有元素的和,有多个这样的询问.
大家看到第一种情况的时候,这不就是前缀和,是的.第二种情况呢,前缀和还能不能用,显然每次修改之后,前缀和就不能使用了,所以又退化为 O(n) 的时间复杂度了.
此时我们就需要用到我们的线段树了.
对于线段树中的每一个非叶子节点[a,b],它的左儿子表示的区间为[a,(a+b)/2],右儿子表示的区间为[(a+b)/2+1,b]。最后的子节点数目为 N,即整个线段区间的长度。
我们看一下 1-10 的线段树是如何存储的.
三、线段树算法的实现
(1)建树
void build(int p, int l, int r) {t[p].l = l, t[p].r = r; // 节点p代表区间[l,r]if (l == r) { t[p].dat = a[l]; return; } // 叶节点int mid = (l + r) / 2; // 折半build(p*2, l, mid); // 左子节点[l,mid],编号p*2build(p*2+1, mid+1, r); // 右子节点[mid+1,r],编号p*2+1// t[p].dat = max(t[p*2].dat, t[p*2+1].dat); // 从下往上传递信息t[p].dat = t[p*2].dat+t[p*2+1].dat; // 从下往上传递信息 }
(2)查询
int ask(int p, int l, int r) {if (l <= t[p].l && r >= t[p].r) return t[p].dat; // 完全包含,直接返回int mid = (t[p].l + t[p].r) / 2;int val = 0;if (l <= mid) val = val+ ask(p*2, l, r); // 左子节点有重叠if (r > mid) val = val+ask(p*2+1, l, r); // 右子节点有重叠return val; }
(3)修改
void change(int p, int x, int v) {if (t[p].l == t[p].r) { t[p].dat = v; return; } // 找到叶节点int mid = (t[p].l + t[p].r) / 2;if (x <= mid) change(p*2, x, v); // x属于左半区间else change(p*2+1, x, v); // x属于右半区间// t[p].dat = max(t[p*2].dat, t[p*2+1].dat); // 从下往上更新信息t[p].dat = t[p*2].dat+t[p*2+1].dat; }
(4)综合代码,求区间和
#include<bits/stdc++.h> using namespace std;const int SIZE=11;int a[11]={0,1,2,3,4,5,6,7,8,9,10}; //原始数据struct SegmentTree {int l, r;int dat; } t[SIZE * 4]; // struct数组存储线段树void build(int p, int l, int r) {t[p].l = l, t[p].r = r; // 节点p代表区间[l,r]if (l == r) { t[p].dat = a[l]; return; } // 叶节点int mid = (l + r) / 2; // 折半build(p*2, l, mid); // 左子节点[l,mid],编号p*2build(p*2+1, mid+1, r); // 右子节点[mid+1,r],编号p*2+1// t[p].dat = max(t[p*2].dat, t[p*2+1].dat); // 从下往上传递信息t[p].dat = t[p*2].dat+t[p*2+1].dat; // 从下往上传递信息 }void change(int p, int x, int v) {if (t[p].l == t[p].r) { t[p].dat = v; return; } // 找到叶节点int mid = (t[p].l + t[p].r) / 2;if (x <= mid) change(p*2, x, v); // x属于左半区间else change(p*2+1, x, v); // x属于右半区间// t[p].dat = max(t[p*2].dat, t[p*2+1].dat); // 从下往上更新信息t[p].dat = t[p*2].dat+t[p*2+1].dat; }int ask(int p, int l, int r) {if (l <= t[p].l && r >= t[p].r) return t[p].dat; // 完全包含,直接返回int mid = (t[p].l + t[p].r) / 2;int val = 0;if (l <= mid) val = val+ ask(p*2, l, r); // 左子节点有重叠if (r > mid) val = val+ask(p*2+1, l, r); // 右子节点有重叠return val; } int main() {//建树从根节点一点一点往下建立,所以第一个参数就是1号编号build(1,1,10);//查询区间[4,7]的和,第一个参数是1的原因是查询要从根节点开始递归int ans=ask(1,4,7);cout<<ans;//修改位置4的值变为25,第一个参数是1的原因是修改也要从根节点开始一步一步往下进行修改change(1,4,25);ans=ask(1,4,7);cout<<ans;return 0;}
(5)综合代码,求区间最大值
#include<bits/stdc++.h> using namespace std;const int SIZE=11;int a[11]={0,1,2,3,4,5,6,7,8,9,10}; //原始数据struct SegmentTree {int l, r;int dat; } t[SIZE * 4]; // struct数组存储线段树void build(int p, int l, int r) {t[p].l = l, t[p].r = r; // 节点p代表区间[l,r]if (l == r) { t[p].dat = a[l]; return; } // 叶节点int mid = (l + r) / 2; // 折半build(p*2, l, mid); // 左子节点[l,mid],编号p*2build(p*2+1, mid+1, r); // 右子节点[mid+1,r],编号p*2+1// t[p].dat = max(t[p*2].dat, t[p*2+1].dat); // 从下往上传递信息t[p].dat = max( t[p * 2].dat , t[p * 2 + 1].dat); // 从下往上传递信息 }void change(int p, int x, int v) {if (t[p].l == t[p].r) { t[p].dat = v; return; } // 找到叶节点int mid = (t[p].l + t[p].r) / 2;if (x <= mid) change(p*2, x, v); // x属于左半区间else change(p*2+1, x, v); // x属于右半区间// t[p].dat = max(t[p*2].dat, t[p*2+1].dat); // 从下往上更新信息t[p].dat = max( t[p * 2].dat , t[p * 2 + 1].dat); }int ask(int p, int l, int r) {if (l <= t[p].l && r >= t[p].r) return t[p].dat; // 完全包含,直接返回int mid = (t[p].l + t[p].r) / 2;int val = 0;if (l <= mid) val = max(val, ask(p * 2, l, r)); // 左子节点有重叠if (r > mid) val = max(val, ask(p * 2 + 1, l, r)); // 右子节点有重叠return val; } int main() {build(1,1,10);int ans=ask(1,4,7);cout<<ans;change(1,4,25);ans=ask(1,4,7);cout<<ans;return 0;}
四、Lazy标记
这种类型的题目,一般都是这样问的:如果每次是对一个区间进行修改,比如让 l,r 区间内的每个值都加 30.然后求和。
如果我们换成对于点的修改,那么时间复杂就太高了.那我们怎么办呢?
我们可以使用 Lazy 标记的方式,进行处理,什么是 Lazy 标记?
若在一次修改操作中发现节点 p 所代表的区间 [pl,pr] 被修改区间 [l,r] 完全覆盖,并且随后的查询操作没有利用到范围 [l,r] 的子区间作为候选答案,那么对节点 p 及其子树进行的更新操作将是没有实际效果的。此情况下,我们需要考虑优化算法,避免对整棵子树进行无意义的更新。
在执行修改指令时,如果发现存在 l < pl < pr < r 的情况,可以立即返回,并在回溯之前向节点 p 添加一个 Lazy 标记,用于表示 '该节点曾被修改,但其子节点尚未被更新'。
在后续的指令中,若需要向下递归至节点 p,应检查节点 p 是否带有标记。如果存在标记,应根据标记信息更新节点 p 的两个子节点,并为这两个子节点添加标记。然后清除节点 p 的标记。
除了在修改指令中直接划分成的 O(logN) 个节点外,对任意节点的修改都延迟到 '在后续操作中递归进入它的父节点时' 再执行。这样一来,每条查询或修改指令的时间复杂度都降低到了 O(logN)。我们将这些标记称为 '延迟标记',它们提供了线段树中从上往下传递信息的方式。通过延迟标记的设计,我们能够更加高效地处理线段树操作。
这种 '延迟' 的思想是设计算法与解决问题时的一个重要思路,它充分利用了操作的特性,避免了不必要的计算,并提升了算法的效率。延迟标记的应用为线段树操作提供了一种优化策略,使得算法的时间复杂度得以降低。
那我们该如何设计呢.
#include <bits/stdc++.h> using namespace std;const int SIZE = 11;int a[11] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // 原始数据struct SegmentTree {int l, r;long long sum, add; } tree[SIZE * 4]; // struct数组存储线段树void build(int p, int l, int r) {tree[p].l = l, tree[p].r = r;if (l == r){tree[p].sum = a[l];return;}int mid = (l + r) / 2;build(p * 2, l, mid); // 构建左子树build(p * 2 + 1, mid + 1, r); // 构建右子树tree[p].sum = tree[p * 2].sum + tree[p * 2 + 1].sum; // 更新节点的区间和 }void spread(int p) {// 下传延迟标记if (tree[p].add){tree[p * 2].sum += tree[p].add * (tree[p * 2].r - tree[p * 2].l + 1);tree[p * 2 + 1].sum += tree[p].add * (tree[p * 2 + 1].r - tree[p * 2 + 1].l + 1);tree[p * 2].add += tree[p].add; // 左子树打延迟标记tree[p * 2 + 1].add += tree[p].add; // 右子树打延迟标记tree[p].add = 0; // 清除延迟标记} }void change(int p, int l, int r, int d) {if (l <= tree[p].l && r >= tree[p].r){// 完全覆盖节点的区间tree[p].sum = (long long)d * (tree[p].r - tree[p].l + 1); // 更新节点的区间和tree[p].add += d; // 打延迟标记return;}spread(p);int mid = (tree[p].l + tree[p].r) / 2;if (l <= mid)change(p * 2, l, r, d); // 修改左子树if (r > mid)change(p * 2 + 1, l, r, d); // 修改右子树tree[p].sum = tree[p * 2].sum + tree[p * 2 + 1].sum; // 更新节点的区间和 }long long ask(int p, int l, int r) {if (l <= tree[p].l && r >= tree[p].r)return tree[p].sum;spread(p);int mid = (tree[p].l + tree[p].r) / 2;long long val = 0;if (l <= mid)val += ask(p * 2, l, r); // 查询左子树if (r > mid)val += ask(p * 2 + 1, l, r); // 查询右子树return val; }int main() {build(1, 1, 10);int ans = ask(1, 4, 7);cout << ans << endl;change(1, 4, 5, 10);ans = ask(1, 4, 7);cout << ans << endl;return 0; }