Range Sum Query - Mutable

描述

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

Given nums = [1, 3, 5]

  1. sumRange(0, 2) -> 9
  2. update(1, 2)
  3. sumRange(0, 2) -> 8

Note:

  • The array is only modifiable by the update function.
  • You may assume the number of calls to update and sumRange function is distributed evenly.

    分析

由于需要求任意段的和，且会随机修改元素，用线段树(Segment Tree)再合适不过了。

另外一个数据结构，树状数组(Binary Indexed Tree)，也适合解这道题。

解法1 线段树

解法2 树状数组

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/binary-tree/segment-tree/range-sum-query-mutable.html