Leetcode 307. 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.

給定一個整型數組，找出數組下标i到j的元素的和。

給定一個更新操作，update(i,val)将第i個元素更新為val。

Example:

Given nums = [1, 3, 5]

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

Note:

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

1. 數組隻能被update方法更改。
2. 假設update和sumRange被均勻調用。

首先嘗試用數組sums的第i個元素存儲[0:i]的和，這樣的話：sumRange的時間複雜度為O(1)，由于每次update(i,val)都要更新下标i之後的sums，是以時間複雜度為O(n)，由于update和sumRange被均勻調用，是以整個操作的時間複雜度為O(n)；另外需要n個元素的存儲空間。

這樣的話，不出意外的TLE了。

考慮用二叉樹存儲部分和。

構造一個完全二叉樹，最後一層存儲原始數組元素，其餘每一層存儲下一層對應左右孩子節點之和，使用二維數組tree[][]存儲這顆完全二叉樹，tree[0]存儲原始數組，tree[i][j]存儲tree[i-1][j*2]和tree[i-1][j*2+1]之和，其中i>0,j>=0；

sumRange(i,j)的求法：

由于i<=j，是以隻需要同時從tree[0][i]和tree[0][j]向上周遊到最近的共同祖先節點pf即可，搜尋過程中以s1記錄以pf為根的這棵樹中i之前所有元素之和，以s2記錄j之前所有元素之和，最後結果就是：s2-s1+tree[0][i]；

s1的更新方法：

若目前周遊的節點i'為父節點i''的右孩子，則另s1加上i''左孩子的值；若為左孩子則不需要更新；

s2的更新方法：

若目前周遊的節點j'為父節點j''的右孩子，則另s2加上j''左孩子的值；若為左孩子則不需要更新；

update(i,val)的操作：

依次按tree[0][i],tree[1][i/2],...的順序一直更新到根節點即可；

複雜度：

class NumArray
{
private:
	vector<vector<int>> tree;
	int rows, cols;
public:
	NumArray(vector<int> &nums)
	{
		int r = 0, c = nums.size();
		if ((cols = c) == 0)
		{
			rows = 0;
			return;
		}

		tree.push_back(nums);
		while (1)
		{
			int size = tree[r].size();
			if (size == 1)		break;

			vector<int> sums;
			for (int i = 0;i < size;i += 2)
			{
				if (i + 1 < size)	
				    sums.push_back(tree[r][i] + tree[r][i + 1]);
				else	
				    sums.push_back(tree[r][i]);
			}
			tree.push_back(sums);
			++r;
		}
		rows = r + 1;
	}

	void update(int i, int val)
	{
		int delta = val - tree[0][i];

		for (int j = 0;j < rows;++j)
		{
			tree[j][i] += delta;
			i = i / 2;
		}
	}

	int sumRange(int i, int j)
	{
		if (i < 0 || i >= cols || j < 0 || j >= cols)	return 0;

		int r, s1, s2, i0, i_, j_;
		r = 0;
		s1 = tree[r][i];
		s2 = tree[r][j];
		i0 = i;

		while (i != j)
		{
			i_ = i / 2;
			j_ = j / 2;

			if (i_ * 2 + 1 == i)	// i is the right child of his parent
			{
				s1 += tree[r][i - 1];
			}
			if (j_ * 2 + 1 == j)	// j is the right child of his parent
			{
				s2 += tree[r][j - 1];
			}
			++r;
			i = i_;
			j = j_;
		}
		return s2 - s1 + tree[0][i0];
	}
};