共计 7650 个字符，预计需要花费 20 分钟才能阅读完成。
欢迎留言！[全网最详细讲解]Part1.OpenJudge 百练 2528:Mayor’s posters Part2. 线段树从简单题到复杂题详细讲解
Part1. 百练 2528:Mayor’s posters
题目链接：http://bailian.openjudge.cn/p…
思路 1：Brute Force，record and keep updating the most outside poster‘s ID. Scan once and count the number of different IDs at last.
Solution 2. Based on Segment-Tree（线段树）.
先理解线段树的基础知识。
建树。每个节点的 id 值（关键值)存储该区域最外层的海报的 id。节点关键值 id 的设置：将 -1 定义为没有海报覆盖，0 代表有多个海报覆盖，id= 1 到 m 代表被第 id 个海报覆盖，线段树只要在 0 时向下深入，其他的直接统计颜色。统计第 id 个可以考虑使用数组模拟位图。查询。在一个路径上不继续往子孙搜索的标志是，这个区域上只被一张海报覆盖或, 即遇到 1 到 m，此时更新位图。遇到 -1，也停止在路径上继续搜索。扫描为位图得到最后结果。Code for Solution 2 :
注意下面 code 中，我用 - 1 表示了有多个海报，0 表示了没有多个海报覆盖，与上面不一致。
// 贴海报, 输出没有被覆盖的个数
include<stdio.h>
struct node
{
int l,r; // 左右孩子的编号
int st,mi,en;
int id;
}; // 线段树简单一维
const int maxN = 50000002; // 线段树的节点个数
const int maxL = 10000020; // 台阶的宽度上限
node segment_tree[maxN]; // 保存着线段树的所有节点
define tree segment_tree
int root, ptr;
void insert(int cr, int start, int end, int color) // 插入到指定区域, 同时初始化沿途的所有节点
{
if(start >= end) // 不符合输入要求
return;
if(tree[cr].st == start && tree[cr].en == end) // 输入区间正好等于节点的表示区间
{tree[cr].id = color; // 这个区间属于该海报
return;
}
int mid = (tree[cr].st + tree[cr].en) / 2;
if(tree[cr].l == 0) // 意味着还没有初始化孩子结点
{
//ptr 代表节点的编号
tree[cr].l = ptr++;
tree[tree[cr].l].l = tree[tree[cr].l].r = 0;
tree[tree[cr].l].id = -1;
tree[tree[cr].l].st = tree[cr].st, // 这里对左右孩子的范围进行初始化
tree[tree[cr].l].en = mid;
}
if(tree[cr].r == 0)
{tree[cr].r = ptr++;
tree[tree[cr].r].l = tree[tree[cr].r].r = 0;
tree[tree[cr].r].id = -1;
tree[tree[cr].r].st = mid,
tree[tree[cr].r].en = tree[cr].en;
}
if(tree[cr].id != 0) // 之后的子区间肯定都属于该海报
{tree[tree[cr].l].id = tree[tree[cr].r].id = tree[cr].id;
tree[cr].id = 0;
}
if(start >= mid){insert(tree[cr].r, start, end, color);
return;
}
if(end <= mid){insert(tree[cr].l, start, end, color);
return;
}
insert(tree[cr].l, start, mid, color);
insert(tree[cr].r, mid, end, color);
}
char exist[10001];
void trail(int cr) // 统计可以看见的节点编号
{
if(cr == 0 || tree[cr].id == -1)
return;
exist[tree[cr].id] = 1; //id 不为 0, 意味着只有它可见, 但之后的节点都看不见了.
if(tree[cr].id != 0) // 不为 0 意味着后面的区域都要被覆盖.
return;
trail(tree[cr].l);
trail(tree[cr].r);
}
// 初始化跟节点
void init()
{
root = 1;
tree[root].l = tree[root].r = tree[root].id = 0;
tree[root].st = 1, tree[root].en = maxL, tree[root].mi = (1 + maxL)/2;
ptr = 2;
}
int main()
{
int test,n,i,l,r;
scanf("%d", &test);
while(test--)
{init();
scanf("%d",&n);
for(i = 1; i <= n; i++)
{scanf("%d%d",&l,&r);
insert(1, l, r+1, i); // 从根节点开始插入
}
for(i = 1; i <= n; i++)
exist[i] = 0;
trail(1);
int ans = 0;
for(i = 1; i <= n; i++)
if(exist[i])
ans++;
printf("%d\n",ans);
}
return 0;
}
Part2. 线段树从简单题到复杂题详细讲解
目录
线段树综述
线段树的更新操作的流程
例题：百练 OJ- 贴海报
本题选择的线段树模型
核心数据结构和算法步骤
c++ 代码实现
线段树综述
线段树，图例：
图 1
这里写图片�述
图 1 的解读:
A[l,r]表示区间 [l,r] , A[t] 表示区间 [t,t]
线段树描述了图中的数组
数组元素个数 N 是叶子节点的个数
2N – 1 是总节点个数
A[l,r] 的取值是对应区间的数值和
叶子节点是单个元素的值
非叶子节点是子节点的和
// 一个区间对应一个节点
struct TreeNode
{
int l,r; // 区间的左边界或右边界
int data; // 区间中的最大值、最小值，区间的极值（最大值减 - 最小值）// 区间最外层覆盖物的 id，id = 0，表示最外层无覆盖物；id = -1 表示最外层上并列了多个覆盖物}node[2*N] // 整个线段树用数组表示
node[i] 的孩子是 node[2i+1] node[2i + 2] // i 从 o 开始
[l,r]根据需要设置为（1）[l,mid]，[mid.r] 或（2）[l.mid],[mid+1,r]。
一般原本离散的模型，如图 1 中的数组选择模型 (2)
后文的贴海报习题将连续模型离散化，需要选择模型 (1), 否则[mid,mid+1] 这个实际存在的连续段没有表示出来。
非叶子节点的意义;
可以是子节点的和，子节点中的最大、最小值等
线段树类似于二叉搜索树、堆
线段树的节点意义. 提示二：小 Hi 大讲堂之线段树的节点意义页面中的提示二部分
应用场景模型：
「区间问题」，通过使用额外的空间（非叶子节点，如图 1）来记录某个区间的值，通过「平衡二叉树」存储对应的数据，使得查询时间复杂度降低到 O（logn）。
「区间问题」：一个区间的和，区间中的最大值、最小值，区间的极值（最大值减 – 最小值）
线段树数据结构的实现;
用数组实现，类比堆的数组实现
以上内容的参考文献：微信文章搜索. 超越技术. 图解线段树
线段树的创建、查询、更新
https://blog.csdn.net/gl48654…
线段树的更新
将 A[4]更新为 666
紫色是查找路径，A[4]的所有祖先的值也要更新，查找可以递归实现，祖先的值可以选择在每次递归结束时更新
待整理：
线段树的创建：微信文章搜索. 超越技术. 今天不学数据结构，学画画
典型题 - 求一堆数据某数据区间的极差，极差 = 最大值 – 最小值
题目描述
在紫金山的路两边有好多树，每棵树的高度记作 h，h 为一个 int 类的正整数，从路的开头到路的尽头对树依次编号
1，2，3，4…n (n<100,000)。现在求[a,b] 从 a 号树到 b 号树高度的极差，就是 [a,b] 中最高树的高度减去最矮树的高度。
解答要求时间限制：2000ms, 内存限制：64MB
输入
第二行正整数 N，Q，分别表示有 N 棵树，Q 表示有 Q(Q<=10000) 次询问。
第三行有 N 个正整数。
下面 Q 行每行有 a，b。分别表示第 a 棵树第 b 棵树(a
输出
对于每次询问输出高树的高度。
样例
输入样例 1 复制
6 3
1 7 3 4 2 5
1 5
4 6
2 2
输出样例 1
6
3
0
// 一个区间对应一个节点
struct TreeNode
{
int l,r; // 区间的左边界或右边界
int maxV; // 区间中的最大值、最小值，区间的极值（最大值减 - 最小值）int minV;}node[2*N] // 整个线段树用数组表示
// 一个区间对应一个节点
class TreeNode {
public:
int l, r; // 区间的左边界或右边界
int maxV; // 区间中的最大值、最小值，区间的极值（最大值减 - 最小值）int minV;
TreeNode(int l, int r) {
this->l = l;
this->r = r;
}
TreeNode() {}};
TreeNode g_node[3 * N]; // 整个线段树用数组表示
// g_node[i] 的孩子是 g_node[2i] g_node[2i + 1] // i 从 1 开始
// [l,r] 的孩子根据需要设置为 (1)[l,mid]，[mid.r] 或 (2) [l.mid],[mid+1,r]，
// 此处选（2），除了后面的“贴海报例题”，一般选(2), 贴海报是连续区间离散化，[mid, mid +1]
// 是实际存在的，不能丢失
int g_A[N];
/ 建树/
TreeNode build(int i, int l, int r) {
g_node[i].l = l;
g_node[i].r = r;
if (l == r) {g_node[i].maxV = g_A[l];
g_node[i].minV = g_A[l];
return g_node[i];
}
int mid = l + (r - l) / 2;
build(2 * i, l, mid);
build(2 * i + 1, mid + 1, r);
g_node[i].maxV = max(g_node[2 * i].maxV, g_node[2 * i + 1].maxV);
g_node[i].minV = min(g_node[2 * i].minV, g_node[2 * i + 1].minV);
return g_node[i];}
/ Query Min /
int queryMin(int i, int l, int r) {// i is the index of a g_node
if (l < g_node[i].l || r > g_node[i].r)// wrong parameters
return -1000;
if (l == g_node[i].l && r == g_node[i].r) return g_node[i].minV;
if (g_node[i].l == g_node[i].r) return g_node[i].minV;// 这里不能写成 if(l == r), 否则在 i=1 时就直接返回 node[i].minV 了。
// if(l == r) return g_node[i].minV; // 错误
int mid = g_node[i].l + (g_node[i].r - g_node[i].l) / 2;
if (r <= mid) return queryMin(2 * i, l, r);
if (l >= mid + 1) return queryMin(2 * i + 1, l, r);
return min(queryMin(2 * i, l, mid), queryMin(2 * i + 1, mid + 1, r));
}
/ Query Max/
int queryMax(int i, int l, int r) {// i is the index of a g_node
if (l < g_node[i].l || r > g_node[i].r)// wrong parameters
return -1000;
if (l == g_node[i].l && r == g_node[i].r) return g_node[i].maxV;
if (g_node[i].l == g_node[i].r) return g_node[i].maxV; // 这里不能写成 if(l == r), 否则在 i=1 时就直接返回 node[i].maxV 了。
// if(l == r) return g_node[i].maxV; // 错误
int mid = g_node[i].l + (g_node[i].r - g_node[i].l) / 2;
if (r <= mid) return queryMax(2 * i, l, r);
if (l >= mid + 1) return queryMax(2 * i + 1, l, r);
return max(queryMax(2 * i, l, mid), queryMax(2 * i + 1, mid + 1, r));
}
int main() {
int n, q, a, b;
cin >> n >> q;
for (int i = 1; i < n + 1; ++i) {scanf("%d", g_A + i);
}
build(1, 1, n);
while (q--) {
cin >> a >> b;
if (a == b) {
cout << 0 << endl;
break;
}
int tmp = a;
a = min(a, b);
b = max(tmp, b);
cout << queryMax(1, a, b) - queryMin(1, a, b) << endl;
}
return 0;}
例题（贴海报）的线段树建模
暴力法：标记每个单元上最外层海报的序号，最后进行统计。时间 O(lgN*K) 空间 O（N+K）总长度 N，海报个数 K
优化方法：线段树方法
本题的线段树建模：
上图线段树中离散的区间是[l,mid],[mid,r] 而不是[l,mid],[mid+1,r]：
至于为什么这样 可以用反证法~~ 如果 [mid,mid+1] 之间有一个海报怎么存贮？
叶子节点个数是 N，则节点总数是 2N
核心数据结构和算法步骤：
node{// a segment
int st; // 开始坐标
int en; // 结束坐标
int id；// 该节点上最外面一层海报的序号。id = 0 表示没有海报覆盖，-1 表示有多个海报覆盖}
typedef segment node;
1. 建树，输入所有海报信息，如果当前 node.id >0 则信息无须继续传递给子节点。时间 O(Klog2N)
2. 统计，A[i] 标记第 i 个线段出现在最外层，从根节点开始递归遍历更新 A[i]信息，如果当前 node.id <= 0, 则无须遍历子节点。时间（log2N）
3. 扫描 A[i]统计最后的结果，O（K）
贴海报的代码实现：
// 贴海报, 输出没有被覆盖的个数
include<stdio.h>
struct node
{
int l,r; // 左右孩子的编号
int st,mi,en;
int id;
}; // 线段树简单一维
const int maxN = 50000002; // 线段树的节点个数
const int maxL = 10000020; // 台阶的宽度上限
node segment_tree[maxN]; // 保存着线段树的所有节点
define tree segment_tree
int root, ptr;
void insert(int cr, int start, int end, int color) // 插入到指定区域, 同时初始化沿途的所有节点
{
if(start >= end) // 不符合输入要求
return;
if(tree[cr].st == start && tree[cr].en == end) // 输入区间正好等于节点的表示区间
{tree[cr].id = color; // 这个区间属于该海报
return;
}
int mid = (tree[cr].st + tree[cr].en) / 2;
if(tree[cr].l == 0) // 意味着还没有初始化孩子结点
{
//ptr 代表节点的编号
tree[cr].l = ptr++;
tree[tree[cr].l].l = tree[tree[cr].l].r = 0;
tree[tree[cr].l].id = -1;
tree[tree[cr].l].st = tree[cr].st, // 这里对左右孩子的范围进行初始化
tree[tree[cr].l].en = mid;
}
if(tree[cr].r == 0)
{tree[cr].r = ptr++;
tree[tree[cr].r].l = tree[tree[cr].r].r = 0;
tree[tree[cr].r].id = -1;
tree[tree[cr].r].st = mid,
tree[tree[cr].r].en = tree[cr].en;
}
if(tree[cr].id != 0) // 之后的子区间肯定都属于该海报
{tree[tree[cr].l].id = tree[tree[cr].r].id = tree[cr].id;
tree[cr].id = 0;
}
if(start >= mid){insert(tree[cr].r, start, end, color);
return;
}
if(end <= mid){insert(tree[cr].l, start, end, color);
return;
}
insert(tree[cr].l, start, mid, color);
insert(tree[cr].r, mid, end, color);
}
char exist[10001];
void trail(int cr) // 统计可以看见的节点编号
{
if(cr == 0 || tree[cr].id == -1)
return;
exist[tree[cr].id] = 1; //id 不为 0, 意味着只有它可见, 但之后的节点都看不见了.
if(tree[cr].id != 0) // 不为 0 意味着后面的区域都要被覆盖.
return;
trail(tree[cr].l);
trail(tree[cr].r);
}
// 初始化跟节点
void init()
{
root = 1;
tree[root].l = tree[root].r = tree[root].id = 0;
tree[root].st = 1, tree[root].en = maxL, tree[root].mi = (1 + maxL)/2;
ptr = 2;
}
int main()
{
int test,n,i,l,r;
scanf("%d", &test);
while(test--)
{init();
scanf("%d",&n);
for(i = 1; i <= n; i++)
{scanf("%d%d",&l,&r);
insert(1, l, r+1, i); // 从根节点开始插入
}
for(i = 1; i <= n; i++)
exist[i] = 0;
trail(1);
int ans = 0;
for(i = 1; i <= n; i++)
if(exist[i])
ans++;
printf("%d\n",ans);
}
return 0;
}
例题 - 计算线段覆盖区域的总长度
微信搜索. 信息学竞赛.OI 省选算法之线段树（1）
