线段树

文章目录

线段树构造线段树使用普通方式求范围和懒惰传播（lazy propagation）使用懒惰传播的方式更新范围值使用懒惰传播的方式求范围和

学习线段树（segment tree）：https://www.youtube.com/watch?v=ZBHKZF5w4YU

学习线段树的懒惰传播（lazy propagation）：https://www.youtube.com/watch?v=xuoQdt5pHj0

首先简单介绍一下什么是线段树，以及为什么要使用线段树。

假设有一个数组，我们需要对该数组执行如下操作（以下全部假设数组下标从$0$开始）：

求一个区间$[low,high]$内的最小值（或者最大值，或者一个区间内元素的和）。修改第$i$项元素。

如果使用普通的数组，执行第一个操作的时间为$O(n)$，执行第二个操作的时间为$O(1)$。

而使用线段树，这两个操作的时间都为$O({\log }_{2}n)$。

构造线段树

线段树与堆排序中的堆有一些类似。线段树中的叶子节点为原数组中的元素。假设我们要维护一个求范围和的线段树，那么这些叶子节点的父节点的值为所有子节点的和。

对于一个长度为$n$的数组，构造一个线段树需要的空间为：

假设$n$为$2$的幂次方，例如$n=4$，那么需要的空间为$2\ast n-1=7$。假设$n$不为$2$的幂次方，例如$n=5$， 那么取离它最近的且大于它的$2$的幂次方的一个数，也就是$8$，那么需要的空间为$2\ast 8-1=15$。

因此，构造一棵线段树所需的最大空间为$4n$。

下面给出C++的简单实现代码，其中n为数组的大小：

int n; int arr[500000]; int segment_tree[4 * 500000]; // construct a segment tree, that is the sum of range. // range[low, high]. void construct_segment_tree(int low, int high, int root) { // leaf if (low == high) { segment_tree[root] = arr[low]; return; } // construct left child and right child int mid = (low + high) / 2; construct_segment_tree(low, mid, 2 * root + 1); construct_segment_tree(mid + 1, high, 2 * root + 2); // construct root segment_tree[root] = segment_tree[2 * root + 1] + segment_tree[2 * root + 2]; }

使用普通方式求范围和

求范围和的方式非常简单，下面是C++的简单实现：

// return the sum of range[q_low, q_high]. int range_sum(int q_low, int q_high, int low, int high, int root = 0) { // total overlap if (q_low <= low && q_high >= high) { return segment_tree[root]; } // no overlap if (q_low > high || q_high < low) { return 0; } // part overlap int mid = (low + high) / 2; return range_sum(q_low, q_high, low, mid, 2 * root + 1) + range_sum(q_low, q_high, mid + 1, high, 2 * root + 2); }

懒惰传播（lazy propagation）

对于一个普通的线段树，更新一个元素的时间为$O({\log }_{2}n)$，而更新一个范围内的元素需要的时间为$O(n{\log }_{2}n)$。

而使用懒惰传播，可以改善对大量元素进行更新所花费的时间。

懒惰传播的目的是最小化操作线段树中节点的次数。

使用懒惰传播的方式更新范围值

使用懒惰传播方式需要维护一个额外的lazy_tree，它的大小与segment_tree相同。关于具体的细节，请观看上面的视频或寻找其他资料。

大致思路有三部分：

当更新一个节点时，更新这个节点本身，但不更新它的子节点，而是将需要更新的值保存在lazy_tree中。当遍历节点时，第一件需要做的事就是：如果这个节点没有被完全更新，则先更新它，并将lazy的值传递给它的两个子节点。当遍历完子节点时，更新节点本身的值。 int n; int arr[500000]; int segment_tree[4 * 500000]; int lazy_tree[4 * 500000]; // update segment tree, lazy. // range[start, end]. void update_segment_tree_range_lazy(int start, int end, int value, int low, int high, int root = 0) { // make sure all propagation is done at root if (lazy_tree[root] != 0) { segment_tree[root] += lazy_tree[root] * (high - low + 1); // if not a leaf node, propagate to children if (low != high) { lazy_tree[2 * root + 1] += lazy_tree[root]; lazy_tree[2 * root + 2] += lazy_tree[root]; } lazy_tree[root] = 0; } // no overlap if (start > high || end < low) { return; } // total overlap if (start <= low && end >= high) { segment_tree[root] += value * (high - low + 1); // std::cout << "value: " << (high - low + 1)*value << "\n"; // if not a leaf node, propagate to children if (low != high) { lazy_tree[2 * root + 1] += value; lazy_tree[2 * root + 2] += value; } return; } // part overlap int mid = (low + high) / 2; update_segment_tree_range_lazy(start, end, value, low, mid, 2 * root + 1); update_segment_tree_range_lazy(start, end, value, mid + 1, high, 2 * root + 2); // after update children, update root node segment_tree[root] = segment_tree[2 * root + 1] + segment_tree[2 * root + 2]; }

需要注意的是，视频中维护的是最小值，这里的代码维护的是范围和。

使用懒惰传播的方式求范围和

思路与上面的使用普通方式类似，唯一的不同之处在于遍历节点时需要先通过lazy_tree更新节点的值。

int n; int arr[500000]; int segment_tree[4 * 500000]; int lazy_tree[4 * 500000]; // return the sum of range[q_low, q_high]. int range_sum_lazy(int q_low, int q_high, int low, int high, int root = 0) { // make sure all propagation is done at root if (lazy_tree[root] != 0) { segment_tree[root] += lazy_tree[root] * (high - low + 1); // if not a leaf node, propagate to children if (low != high) { lazy_tree[2 * root + 1] += lazy_tree[root]; lazy_tree[2 * root + 2] += lazy_tree[root]; } lazy_tree[root] = 0; } // total overlap if (q_low <= low && q_high >= high) { return segment_tree[root]; } // no overlap if (q_low > high || q_high < low) { return 0; } // part overlap int mid = (low + high) / 2; return range_sum_lazy(q_low, q_high, low, mid, 2 * root + 1) + range_sum_lazy(q_low, q_high, mid + 1, high, 2 * root + 2); }