Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"workbook":{"problemsBrief":"{\"洛谷-P4513\":[\"小白逛公园\",11129,null],\"洛谷-P3722\":[\"影魔\",1738,\"AH2017/HNOI2017\"],\"洛谷-P5327\":[\"语言\",1447,\"ZJOI2019\"],\"洛谷-P4588\":[\"数学计算\",9860,\"TJOI2018\"],\"洛谷-P4556\":[\"雨天的尾巴 /【模板】线段树合并\",11937,\"Vani有约会\"],\"洛谷-P1502\":[\"窗口的星星\",6056,null],\"洛谷-P2824\":[\"排序\",7981,\"HEOI2016/TJOI2016\"],\"洛谷-P5490\":[\"扫描线\",20452,\"模板\"],\"洛谷-P3372\":[\"线段树 1\",157579,\"模板\"],\"洛谷-P3373\":[\"线段树 2\",65997,\"模板\"],\"洛谷-P4198\":[\"楼房重建\",6813,null],\"洛谷-P2471\":[\"降雨量\",5817,\"SCOI2007\"],\"洛谷-P4097\":[\"李超线段树 / [HEOI2013] Segment\",6925,\"模板\"],\"洛谷-P5324\":[\"删数\",1022,\"BJOI2019\"]}","joined":false,"groups":{}},"managingGroups":{},"author":"Exile_code","updateTime":1706767432000,"title":"进阶算法入门(线段树)","dislikeCnt":0,"content":"原文链接:http://t.csdnimg.cn/aU4WS\n\nvjudge显示不了图片,自己插入还要图床,真的服。vjudge写个文章是真的麻烦,我自己上传一直显示稍后再来,死活上传不了,只能让继源传了。最nt的是居然不会自动存草稿,写半天的东西刷新一下就全没了。\n\n# 进阶算法入门(线段树)\n\n在了解线段树之前,我们先需要知道为什么需要线段树,构建线段树的意义是什么\n\n## 线段树的意义\n\n在解决区间问题的查询和修改时,通常会遇到查找和修改发生冲突的问题,想要快速查找,就必须选择不宜修改的存储方式,想要快速修改,就必须选择不宜查找的存储方式。\n\n例:\n\n![img](https://img-blog.csdnimg.cn/7e9e2e293af4406680ac3786b7fdc9d2.png)\n\n对于数组$$arr\u003d|1,2,3…n|$$来说,如果我们使用数组来存储每个元素,如果查询长度为m的区间的所有元素之和,就需要O(m)级别的时间来进行查询,如果要修改其中的一个值,就只需要花费O(1)级别的时间。\n\n为了解决查询时间复杂度过高的问题,我们只需要计算出它的元素和数组就行,这样对于查询任何一个区段的元素之和,时间复杂度都变成了O(1)。\n\n![img](https://img-blog.csdnimg.cn/3a351c3d7e2540f5ab64d09f2d57037d.png)\n\n如果我们并不需要修改数组,这种做法就是完美的,但是,如果我们需要修改数组,我们就会发现更新sumarr的时间复杂度是O(n)。\n\n就像一个天平一样,如果注重查询区间,那必然不易维护,如果注重修改,那必然不易查询区间。\n\n![img](https://img-blog.csdnimg.cn/81c3477be6884377a70c0d6971371819.png)\n\n这个时候,有没有一种结构,可以让天平变得相对平衡呢?\n\n线段树,就给出了解答。\n\n## 线段树的构建\n\n### 从零理解如何构建出线段树\n\n对于元素和数组来说,我们可以将其看成由n个区间和组成的长度为n的数组。\n\n![img](https://img-blog.csdnimg.cn/8088a7aba37d45df83b05a1cb1c3e8d6.png)\n\n对此,就不难理解为什么维护元素和数组的时间复杂度这么高了。\n\n那么,对于这个数组有什么方式可以改进呢?\n\n对于O(n),我们想要进一步优化的话就要优化成为$$O(log n)(O(1)$$在之前已经论证了是行不通的),我们可以很容易联想到二分来进行优化。\n\n例如对数组1,2,3,4,5,6,7,8,9,10\n\n使用二分对区间进行划分,得到:\n\n![img](https://img-blog.csdnimg.cn/09d5fe36af3547b886ddacf8920d98d1.png)\n\n面对这样的区间划分,我们可以联想到什么?\n\n对,二叉树。\n\n使用二叉树的形式来存储我们使用二分划分后的区间。\n\n对于一个长度为10的数组,我们使用二叉树的形式来进行存储\n\n![img](https://img-blog.csdnimg.cn/0d886a6198a742d8928900249a4f5522.png)!\n\n观察这颗二叉树,不难发现,如果去除最下面一层,这就是一颗满二叉树。\n\n对于满二叉树来说,最适合的存储方式,就是顺序存储。所以,我们可以用顺序存储的二叉树来存储我们划分好的区间。\n\n### 线段树的空间复杂度分析\n\n#### 节点数\n\n对于长度为n的数列,对其进行二分区间划分,得到$$n+\\frac{n}{2}+\\frac{n}{4}+\\frac{n}{8}+…+1$$个节点,约为$$2n(\\leq2n)$$,所以空间复杂度为O(n)。\n\n#### 深度:\n\n除去最后一层以外,可以看做满二叉树,所以深度depth为$$log_{2}(n-1)+1。$$\n\n### 线段树的时间复杂度分析\n\n#### 对于查询操作:\n\n例如对于长度为10的线段树,我们查询最极限的情况,区间[1,9]之和,只需要查询[2,2],[3,3],[4,5],[6,8],[9,9]这五个区间。\n\n对于查询区间[l,r],我们最多沿着线段树从顶层走到底层两遍。例如对于最极限的情况,查询区间[2,n-1],我们最多沿着线段树向下两次2×depth所以时间复杂度为$$O(log_{2}{n})$$。\n\n图示:\n\n#### ![img](https://img-blog.csdnimg.cn/3f17e933be6343dea30a5a226396ff1b.png)\n\n#### 对于修改操作:\n\n例如对于长度为10的线段树,我们修改[6,6]的值,需要更新的区间是[6,6],[6,7],[6,8],[6,10],[1,10]这五个区间。\n\n对于查询区间[l,r],我们最多沿着线段树从底层走到顶层一遍。例如对于最极限的情况,修改区间[1,1],我们最多沿着线段树向上一次depth所以时间复杂度为$$O(log_{2}{n})$$。\n\n图示:\n\n### ![img](https://img-blog.csdnimg.cn/e8e40ce5180442fcbd8df027d208c897.png)\n\n### 构建线段树代码:\n\n```\nconst int N;//N为数组长度\n\nll st[4 * N]{ 0 };//考虑极限情况,最后一层可能有2N个空位,所有要开4N大小的数组来存储线段树\n\nvoid build(int l, int r, int p)//l为当前左边界,r为当前右边界,p为线段树当前编号\n{\n //如果l和r相等,表示已经到了叶节点,直接返回。\n if (l \u003d\u003d r)\n {\n st[p] \u003d nums[l];\n return;\n }\n //二分递归建树\n int mid \u003d (l + r) / 2;\n build(l, mid, p * 2);\n build(mid + 1, r, p * 2 + 1);\n st[p] \u003d st[p * 2] + st[p * 2 + 1];//递归更新\n}\n```\n\n## 线段树的操作:\n\n### 1、查询区间和\n\n```\nll getSum(int x, int y, int l, int r, int p)//x,y为待查询区间[x,y]的左右边界\n{\n if (x \u003c\u003d l \u0026\u0026 r \u003c\u003d y)//如果当前节点被包含,直接返回当前节点的值\n return st[p];\n int mid \u003d (l + r) / 2;\n ll sum \u003d 0;\n if (x \u003c\u003d mid)//中间值大于等于左边界,表示左半界需要查询\n sum +\u003d getSum(x, y, l, mid, p * 2);\n if (mid \u003c y)//中间值小于右边界,表示右边界需要查询,等于则表示没有右半界了\n sum +\u003d getSum(x, y, mid + 1, r, p * 2 + 1);\n return sum;\n}\n\n```\n\n### 2、修改指定单点\n\n```\nvoid changeNode(int pos, int v, int l, int r, int p)//pos为目标位置,v为目标值\n{\n if (l \u003d\u003d r)\n {\n st[p] \u003d v;\n return;\n }\n int mid \u003d (l + r) / 2;\n if (pos \u003c\u003d mid)//pos在左子树\n changeNode(pos, v, l, mid, p * 2);\n else//pos在右子树\n changeNode(pos, v, mid + 1, r, p * 2 + 1);\n st[p] \u003d st[p * 2] + st[p * 2 + 1];//递归回溯更新\n}\n```\n\n### 3、修改指定区间\n\n如果使用单点修改的方式,还不如模拟,所以需要使用延迟修改的方法。\n\n![img](https://img-blog.csdnimg.cn/e5c6b624dafa45dc9c81128e3048ddca.png)\n\n只要不查询[4,4],[4,4],[4,7],[8,8]就不对它们进行修改。\n\n那怎么保证查询到[4,4],[4,4],[4,7],[8,8]时同时对它们进行修改呢?我们可以维护一个tag数组,表示当前节点含有延迟修改的值。\n\n```\nvoid checkDelay(int l, int r, int p)//检测函数,检查当前节点是否有延迟标记,有则传递给子树\n{\n if (!tag[p])\n return;\n int mid \u003d (l + r) / 2;\n tag[p * 2] \u003d tag[p * 2 + 1] \u003d tag[p];\n st[p * 2] \u003d (mid - l + 1) * tag[p];\n st[p * 2 + 1] \u003d (r - mid) * tag[p];\n tag[p] \u003d 0;//清空tag\n}\n\nvoid changeInterval(int x, int y, int v, int l, int r, int p)//区间修改\n{\n if (x \u003c\u003d l \u0026\u0026 r \u003c\u003d y)\n {\n tag[p] \u003d v;\n st[p] \u003d v * (r - l + 1);\n return;\n }\n checkDelay(l, r, p);//检测是否有延迟标记\n int mid \u003d (l + r) / 2;\n if (x \u003c\u003d mid)\n changeInterval(x, y, v, l, mid, p * 2);\n if (mid \u003c y)\n changeInterval(x, y, v, mid + 1, r, p * 2 + 1);\n st[p] \u003d st[p * 2] + st[p * 2 + 1];\n}\n```\n\n注:\n\n如果使用了延迟修改的话,所有查询工作都需要加上延迟标记检测\n\n### 4、指定区间加值\n\n需要额外维护一个tag数组来表示乘法\n\n```\n//使用宏定义减少书写\n#define ls p*2//左子树所在位置\n#define rs p*2+1//右子树所在位置\n#define mid (l+r)\u003e\u003e1\n\nstruct Node\n{\n ll v;//区间和的值\n ll add;//加法tag\n ll mul;//减法tag\n}sumST[4 * N];\n\nvoid checkTag(int l, int r, int p)//要注意优先级的统一,这里设置的是加法优先结算和运算\n{\n int m \u003d mid;\n //更新区间和的值\n sumST[ls].v \u003d (sumST[ls].v * sumST[p].mul + sumST[p].add * (m - l + 1));\n sumST[rs].v \u003d (sumST[rs].v * sumST[p].mul + sumST[p].add * (r - m));\n \n //更新tag\n sumST[ls].mul \u003d (sumST[ls].mul * sumST[p].mul);\n sumST[rs].mul \u003d (sumST[rs].mul * sumST[p].mul);\n sumST[ls].add \u003d (sumST[ls].add * sumST[p].mul + sumST[p].add);//注:这里代表加法优先结算,后面也需要同样先结算\n sumST[rs].add \u003d (sumST[rs].add * sumST[p].mul + sumST[p].add);\n \n //清空tag\n sumST[p].mul \u003d 1;\n sumST[p].add \u003d 0;\n}\n\nvoid intervalMultiply(int x, int y, int k, int l, int r, int p)\n{\n if (r \u003c x || y \u003c l)\n return;\n if (x \u003c\u003d l \u0026\u0026 r \u003c\u003d y)\n {\n sumST[p].mul \u003d (sumST[p].mul * k);\n sumST[p].add \u003d (sumST[p].add * k);//加法优先结算\n sumST[p].v \u003d (sumST[p].v * k);\n return;\n }\n checkTag(l, r, p);\n int m \u003d mid;\n if (x \u003c\u003d m)\n intervalMultiply(x, y, k, l, m, ls);\n if (mid \u003c y)\n intervalMultiply(x, y, k, m + 1, r, rs);\n sumST[p].v \u003d (sumST[ls].v + sumST[rs].v);//更新线段树\n}\n```\n\n### 5、查询指定区间的最小值\n\n我们就只要维护一个区间最小值的线段树就行\n\n```\n//建一个区间最小值的线段树\nvoid buildMinNum(int l, int r, int p)//l为当前左边界,r为当前右边界,p为线段树当前节点的索引\n{\n //如果l和r相等,表示已经到了叶节点,直接返回。\n if (l \u003d\u003d r)\n {\n sum[p] \u003d nums[l];\n return;\n }\n //二分递归建树\n int mid \u003d (l + r) / 2;\n buildMinNum(l, mid, p * 2);\n buildMinNum(mid + 1, r, p * 2 + 1);\n sum[p] \u003d min(sum[p * 2] , sum[p * 2 + 1]);//维护最小值\n}\n\nint getMin(int x, int y, int l, int r, int p)//x,y为待查询区间[x,y]的左右边界\n{\n if (x \u003c\u003d l \u0026\u0026 r \u003c\u003d y)//如果当前节点被包含,直接返回当前节点的值\n return minNum[p];\n checkDelay(l, r, p);\n int mid \u003d (l + r) / 2;\n int mn \u003d 0;\n if (x \u003c\u003d mid)//中间值大于等于左边界,表示左半界需要查询\n mn \u003d min(mn, getMin(x, y, l, mid, p * 2));\n if (mid \u003c y)//中间值小于右边界,表示右边界需要查询,等于则表示没有右半界了\n mn \u003d min(mn,getMin(x, y, mid + 1, r, p * 2 + 1));\n return mn;\n}\n```\n\n### 总结\n\n观察上面五种操作可以发现,线段树各种操作的核心在于递归更新和延迟检测,所有的操作都是基于这两个核心修改而来\n\n## 学习链接\n\n[线段树入门【力扣双周赛 79】LeetCode_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV18t4y1p736/?vd_source\u003d204bd6a950e12dc2a5fd501f88a334d9)\n\n[C02【模板】线段树+懒标记 Luogu P3372 线段树 1_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV1G34y1L7b3/?vd_source\u003d204bd6a950e12dc2a5fd501f88a334d9)\n\n[线段树专精up:董晓算法](https://space.bilibili.com/517494241)讲了一系列线段树的题目,强烈推荐\n\n## 题目练习\n\n[problem:洛谷-P3372],[problem:洛谷-P3373],[problem:洛谷-P5490],[problem:洛谷-P4588],[problem:洛谷-P1502],[problem:洛谷-P2471],[problem:洛谷-P2824],[problem:洛谷-P3722],[problem:洛谷-P4097],[problem:洛谷-P4198],[problem:洛谷-P4513],[problem:洛谷-P4556],[problem:洛谷-P5324],[problem:洛谷-P5327]","threadId":181202,"likeCnt":0,"createTime":1706767432000,"isWorkbook":true,"viewCnt":281,"openness":2,"fav":false,"id":4544,"trustable":false}