附例题【LeetCode】一文吃透线段树

线段树深入浅出，一文吃透！
本文大部分内容来自 LFool? 的力扣题解：，小部分来自线段树 – 新手篇，这里记录只为学习留用，侵删！
最新的内容请移步 -线段树.md
0. 定义
线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点，对于线段树中的每一个非叶子节点 [a, b], 它的左儿子表示的区间为 [a, (a+b)/2], 右儿子表示的区间为 [(a+b)/2+1, b] 。因此线段树是平衡二叉树，最后的子节点数目为 N，即为整个线段区间的长度。
使用线段树可以快速的查找一个节点在若干条线段中出现的次数，时间复杂度为 O(logN)，而未优化的空间复杂度为 2N，因此有时需要离散化让空间压缩
线段树解决的是「区间和」问题，并且该「区间」会被修改。例如对于一个数组，多次求某个区间的和，可以使用「前缀和」实现，但是如果区间里面的元素经常变化时「前缀和」的效率就没那么高效。为此引入线段树，线段树中的每个节点代表一个区间，对于数组 nums=[1, 2, 3, 4, 5] 对应的线段树为：
说明：
每个节点代表一个区间，节点的值就是该区间的和节点的值可以根据题目要求换成自己满足 “区间加法” 的表示，例如有些不符合 “区间加法” 的表示需要注意，例如：根节点代表的区间是问题的总区间，例如上图中数据的长度就是 [0, 4]线段树是一棵近似的完全二叉树，如上图，但也有不是完全二叉树的情况建立线段树的过程就是不断把区间 “平分” 的过程，直到区间长度为1 1. 基本操作
数据结构：由于线段树是一棵近似的完全二叉树，因此可以使用二叉树的结构表示
class Node {int val; // 当前节点值Node* left, *right; // 左右孩子节点Node(int a=0): val(a), left(nullptr), right(nullptr) {};~Node() {delete left;delete right;}}
建立线段树
如果题目中给了具体的区间范围，我们可以根据范围建立线段树
void buildTree(Node* node, int start, int end) {// 到达叶子节点if (start == end) {node->val = arr[start];return ;}int mid = (start + end) / 2;buildTree(node->left, start, mid);buildTree(node->right, mid+1, end);// 向上更新pushUp(node);}void pushUp(Node* node) {node->val = node->left->val + node->right->val;}
【附例题【LeetCode】一文吃透线段树】对于没有具体范围的情况，一般只有数据的取值范围，一般都很大，可以使用「动态开点」，例如刚开始我们只知道数组的长度为5，不知道数组内每个元素的大小，元素都是一个一个添加进去的，此时需要动态开点，例如刚开始的节点就只能是 [0, 4]; val = 0，此时添加元素 [2, 2]; val = 3，线段树变为：
这里需要解释一下，如果一个节点没有左右孩子，会一下子把左右孩子节点都给创建出来，如上图橙色节点所示，具体代码可见方法 ()
两个橙色的叶子节点仅仅只是被创建出来了，并无实际的值，均为 0；而另外一个橙色的非叶子节点，值为 3 的原因是下面的孩子节点的值向上更新得到的
下面给出依次添加剩余节点的过程：(注意观察值的变化！！)

文章插图
「动态开点」一般是在「更新」或「查询」的时候动态的建立节点，具体可见下面的更新和查询操作
更新线段树：将指定区间如 [2, 4] 的元素都增加1
更新的前提是查询需要更新的区间，首先查找到区间 [2, 2] 和 [3, 4]，然后更新节点，但是如果只是更新这两个节点的话也有问题，因为 [3, 3] 和 [4, 4] 也需要更新，当查询它们时才可以得到更新之后的值。

附例题 【LeetCode】一文吃透线段树

附例题【LeetCode】一文吃透线段树