全网最详细讲解Part1OpenJudge百练2528Mayors-posters-线段树

jiezi

5 年前

欢迎留言！[全网最详细讲解]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 表示了没有多个海报覆盖，与上面不一致。

// 贴海报, 输出没有被覆盖的个数

struct node

{

int l,r; // 左右孩子的编号  

int st,mi,en;  

int id;

}; // 线段树简单一维

const int maxN = 50000002; // 线段树的节点个数

const int maxL = 10000020; // 台阶的宽度上限

node segment_tree[maxN]; // 保存着线段树的所有节点

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）

贴海报的代码实现：