归档 2015年8月13日

线段树 | 第1讲 (给定区间求和)

让我们通过考虑下面的问题来理解线段树。

给定一个数组arr[0 . . . n-1],我们要对数组执行这样的操作:

1 计算从下标l到r的元素之和,其中 0 <= l <= r <= n-1
​2 修改数组指定元素的值arr[i] = x,其中 0 <= i <= n-1

一个简单的方案是从lr执行循环,计算给定区间的元素之和。更新值的时候,简单地令arr[i] = x。第一个操作花费O(n)的时间,第二个操作花费O ...

继续阅读

昨天

明天

归档