【数据结构】线段树（Segment Tree）
【题目】给定一个数组arr，数组可能非常大。在程序运行过程中，你可能要做好几次query和update操作：
query(arr, L, R) 表示计算数组arr中，从下标L到下标R之间的所有数字的和。
update(arr, i, val) 表示要把arr[i]中的数字改成val。
怎样尽可能快地完成一系列query和update的操作？
线段树可以在花费一些额外空间的情况下，把这两个操作的时间复杂度都控制在O(log(n))。这段视频主要和大家分享线段树的原理和代码实现。
顶部