LeetCode #307 Range Sum Query — Mutable
Problem
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]sumRange(0, 2) -> 9
update(1, 2)
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.
Solution — Segment Tree
It will reach the time limit if we use the brute force approach, which sums up each element in the given query range every time. It will take O(n) for each query and waste too much time.
By adopting the Segment Tree approach, operations of update and query can be significantly reduced.
Complexity
Because counts of nodes in the segment tree are 2n and we update n nodes at once, it will take O(n) time for building the segment tree if n denotes to counts of nodes in the given list nums.
For update and query operations, they both update nodes on a path from the root to leaf, so their time complexity will both be O(logn).
Solution — Binary Indexed Tree
It’s also known as Fenwick Tree with less operation of manipulations and memory allocation. Also, it’s easier to implement.
Complexity
For update and query operations, they both manipulate the current node and all its parent/child nodes, so their time complexity will be O(logn) if n denotes to counts of nodes in the given nums.
And according to this post, we can build the thee in O(n) time.
