p1168线段树解法

时间: 2023-11-14 08:02:19 浏览: 93

线段树详解

### 线段树详解 #### 一、线段树定义与结构 **定义：** 线段树是一种高效的数据结构，常被用于处理区间查询或更新的问题。它是一棵二叉树，其中每个节点代表一个特定的区间。具体来说： - **叶子节点**：代表一个单位区间，即形式为`[i, i]`的区间。 - **非叶子节点**：代表两个子区间之并，例如节点代表区间`[a, b]`，则它的左子节点代表`[a, (a+b)/2]`，右子节点代表`[(a+b)/2 + 1, b]`。 **举例说明：** 假设我们有一个区间`[1, 10]`，那么构建出来的线段树将如下所示： ``` [1, 10] ├─ [1, 5] ── [5, 10] │ ├─ [1, 3] ── [3, 5] │ │ ├─ [1, 2] ── [2, 3] │ │ │ ├─ [1, 1] ── [2, 2] │ │ │ └─ [3, 3] ── [3, 4] │ │ └─ [4, 4] ── [5, 5] │ └─ [5, 6] ── [6, 7] │ ├─ [5, 5] ── [6, 6] │ └─ [7, 7] ── [7, 8] └─ [7, 9] ── [8, 10] ├─ [7, 7] ── [8, 8] └─ [9, 9] ── [9, 10] ``` #### 二、线段树的应用 **信息域：** 为了使线段树更加灵活，通常会在每个节点上添加额外的信息，如最大值、最小值、总和等，这使得线段树能够支持多种操作。 **常见应用场景：** 1. **区间查询**：例如求某区间内元素的最大值、最小值或总和。 2. **区间更新**：批量修改区间内元素的值。 #### 三、线段树的数据结构实现 **1. 动态数据结构（指针实现）** **节点结构体：** ```c++ struct Node { int left, right; // 区间的左右边界 Node *leftChild, *rightChild; // 左右子节点 KeyType key; // 存储额外信息 }; ``` **建空树：** ```c++ Node* buildTree(int a, int b) { Node *p = new Node; p->left = a; p->right = b; // 初始化 p->key if (b - a == 1) return p; int mid = (a + b) / 2; p->leftChild = buildTree(a, mid); p->rightChild = buildTree(mid, b); return p; } ``` **插入线段：** ```c++ void insert(Node *p, int a, int b, KeyType key) { if (a <= p->left && p->right <= b) { // 更新 p->key return; } int m = (p->left + p->right) / 2; if (a <= m) insert(p->leftChild, a, b, key); if (b > m) insert(p->rightChild, a, b, key); // 更新 p->key } ``` **查找线段的key值：** ```c++ KeyType search(Node *p, int a, int b) { KeyType res; if (a <= p->left && p->right <= b) { // 更新 res return res; } int m = (p->left + p->right) / 2; if (a <= m) { // 更新 res } if (b > m) { // 更新 res } return res; } ``` **2. 完全二叉树** **节点结构体：** ```c++ struct Node { int left, right; int key; } tree[4 * MAXN]; ``` **创建线段树：** ```c++ void buildTree(int left, int right, int p) { tree[p].left = left; tree[p].right = right; tree[p].key = 0; if (left == right) return; int m = (left + right) / 2; buildTree(left, m, 2 * p); // 创建左子树 buildTree(m + 1, right, 2 * p + 1); // 创建右子树 } ``` **更新线段树：** ```c++ void insert(int d, int p) { if (tree[p].left == tree[p].right && d == tree[p].left) { tree[p].count += 1; return; } int m = (tree[p].left + tree[p].right) / 2; if (d <= m) ``` #### 四、点树的简单应用——求第k小数 **应用场景：** 求解某一有序序列中的第k小的数。 **结点结构体：** ```c++ struct Node { int left, right; int count; // 存放此节点值，默认为0 } tree[3 * MAXN]; ``` **创建线段树：** ```c++ void buildTree(int left, int right, int p) { tree[p].left = left; tree[p].right = right; tree[p].count = 0; if (left == right) return; int m = (left + right) / 2; buildTree(left, m, 2 * p); // 创建左子树 buildTree(m + 1, right, 2 * p + 1); // 创建右子树 } ``` **更新线段树：** ```c++ void insert(int d, int p) { if (tree[p].left == tree[p].right && d == tree[p].left) { tree[p].count += 1; return; } int m = (tree[p].left + tree[p].right) / 2; if (d <= m) { // 更新左子树 } else { // 更新右子树 } // 更新父节点count } ``` **查询线段树：** 查询过程中，可以根据当前节点的`count`属性来判断是否已经找到了第k小的数，并相应地向左子树或右子树递归查询。通过上述内容，我们可以看到线段树不仅能够高效地处理区间查询和更新操作，而且其灵活性还使得它能应用于各种复杂的场景之中。无论是对于初学者还是专业程序员而言，掌握线段树都是非常有价值的。

根据引用\[1\]中的描述，p1168问题使用了线段树解法。在构造树的过程中，需要遍历整棵树，所以时间复杂度为O(n)。但是在改变一个元素的值时，时间复杂度只有O(log(n))。求和的时候，树的节点表示一个索引范围内元素值之和，只要将区间分割对应上，平均时间复杂度是O(log(n))，最坏情况下不会超过O(n*log(n))。\[1\] 根据引用\[2\]中的描述，QUERY 5 12应该是第4、5条边的极大值。\[2\] 根据引用\[3\]中的描述，代码中的if(L<=MID)和else if(R>MID)的判断条件是为了确保查询范围在左子树或右子树中。如果加上else，会导致错误。\[3\] #### 引用[.reference_title] - *1* [leetCode307：线段树解法](https://blog.csdn.net/cyd1999/article/details/123963164)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^koosearch_v1,239^v3^insert_chatgpt"}} ] [.reference_item] - *2* *3* [Spoj 375 Qtree 树链剖分 + 线段树解法](https://blog.csdn.net/niuox/article/details/8145842)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^koosearch_v1,239^v3^insert_chatgpt"}} ] [.reference_item] [ .reference_list ]

阅读全文

p1168线段树解法

相关推荐

线段树算法

洛谷P1168 中位数线段树解法

用c++做线段树 (1)数列中某连续一段全部+1 (2)求数列中某连续一段的最小值，并输出这个值

p1713 士兵排队问题

洛谷p1428 小鱼比可爱

P3157 [CQOI2011] 动态逆序对

【java毕业设计】应急救援物资管理系统源码（springboot+vue+mysql+说明文档）.zip

基于java的音乐网站答辩PPT.pptx

基于Flexsim的公路交通仿真系统.zip

weixin073智慧旅游平台开发微信小程序+ssm后端毕业源码案例设计.zip

python017基于Python贫困生资助管理系统带vue前后端分离毕业源码案例设计.zip

【创新未发表】Matlab实现粒子群优化算法PSO-GRU实现风电数据预测算法研究.rar

基于Android的天文观星系统的设计与实现app.zip

weixin102旅游社交微信小程序+ssm后端毕业源码案例设计.zip

【创新未发表】Matlab实现能量谷优化算法EVO-Kmean-Transformer-BiLSTM负荷预测算法研究.rar

【上交所-2024研报】京城股份2024年三季度报告.pdf

mobilenetv2-12.onnx

非常好的电子设计小软件PCtoLCD2002完美版非常好用的软件.zip

最新推荐

线段树及其应用pptppt

线段树和树状数组入门介绍

线段树解析与经典例题.ppt

【java毕业设计】应急救援物资管理系统源码（springboot+vue+mysql+说明文档）.zip

Android圆角进度条控件的设计与应用

管理建模和仿真的文件

【R语言lattice包实战】：从案例到技巧，图形制作不再难

输入正整数n.打出长度为n的菱形

mui框架实现带侧边栏的响应式布局

"互动学习：行动中的多样性与论文攻读经历"

用c++做线段树　(1)数列中某连续一段全部+1 　　(2)求数列中某连续一段的最小值，并输出这个值