【算法】线段树详解_算法 线段树

一.概述

在说线段树之前，我们先来了解一个问题

给你一串数组a，求一段区间[L，R]的和，该数组的值随时可以更新

传统的做法:
 每次查询某一区间的和，我们声明一个变量sum=0，然后令i从L枚举到R，依此加上a[i]，但是这时候的查询时间复杂度为O(n)
原数组更新时，例如让第i个数改为5，我们只需要直接令a[i]=5就能完成更新，此时更新的时间复杂度为O(1)

前缀和做法：
 这时候很多人会想到直接声明一个数组sum，先预处理出前缀和，然后直接访问sum[R]-sum[L-1]就是所求值，此时一查询的时间复杂度为O(1)
 但是，如果原数组的数据更新呢？这时候直接用前缀和的知识来写，我们每更新一次数组，都要更新前缀和，时间复杂度达到O(n)

总结
无论是传统做法还是前缀和算法，查询或者更新总有一个时间复杂度达到O(n)，当数据大点的时候，就容易超时。那么我们有没有一种算法，让查询和更新的时间复杂度都小于O(n)呢？这里就要介绍本次文章的主角——线段树

二.线段树

 线段树，是一个二叉搜索树，它的主要思想是将一个大的区间上的问题分解为左右两个小区间的问题求解，进而求解出大的区间上的答案。例如，我们想要求解区间长度为10上的问题，它构造出来的线段树如下图所示

 可以看出，每次线段树的深度最大不会超过⌊$\log (n)+1$⌋,如此一来，其查询的时间复杂度为O($\log (n)$)，其更新操作的时间复杂度也是O($\log (n)$)

线段树的编写

假设有一串数组a，长度为[L, R]，对于线段树的编写，有以下基本步骤

1. 计算出区间的中点mid，将区间分为两个小区间[L, mid], [mid+1, R]
2. 对两个区间递归分解，直到区间长度为1，得到这个区间的答案
3. 依此回溯得到大区间的答案
4. 最终得到[L, R]的答案

可能有的人看到这还是有点懵懂，接下来我们来根据一道例题来讲解

假设有一个数组a[]={1，2，3，4，5，6，7，8，9，10}，我们要进行区间求和，接下来我们来构造线段树，先把区间分成这样一个形式

从下往上计算答案

计算第4层答案，有子元素的为子元素的和

第三层，第二层，第一层同理，最后得到下图

这样我们线段树的构造完成了！
那么，构造完线段树，我们都是怎么进行查询的呢？假设总的区间长度为[start, end]，要查询的区间为[L, R]。
一般来说，查询的步骤如下

1. 当前区间为[start, end]时，如果L<=start且R>=end，则返回当前区间的答案
2. 否则计算出[start, end]的中点mid. 如果L<=mid，则向[start, mid]搜索答案，R>mid时向[mid+1, end]搜索答案
3. 重复1，2步，直到将答案搜索到

例如，我们要求解[4,9]之间的区间和是多少时
1.因为[1,10]的中点为5，而4<5而9>5，所以我们向两边搜索答案，如下图，红色为判断过的，绿色为还未判断

在区间[1,5]，中点mid=3，又因为L>mid, 但是R>mid，所以只向右孩子搜索
同理对区间[6,10]，中点mid=8，因为L<mid且R>mid所以向两个孩子都搜索，如下图

对[4,5]，因为L&l