LeetCode 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]
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.

---

给定一个一维数组，要求实现范围求和，即求[i,j]之间的元素的和。sumRange(i,j)求i~j的元素和，update(i,val)更新下标为i的元素值为val。 第一敏感使用线段树，很久之前在hihoCoder上遇到过。 建树的方法是类似于树的后序遍历，即左右根。不断把[start,end]二分，构建左右子树，然后构建当前节点，当前节点的sum等于左右子树的sum的和。在递归的时候，递归到start==end时，说明只有一个元素了，此时sum就等于该元素。 查询的方法和建树方法类似，判断区间[i,j]和区间[start,end]的关系，假设start和end的中点是mid，如果j<=mid，递归在左子树查询；如果i>mid，递归在右子树查询；否则在[i,mid]和[mid+1,j]查询然后求和。 更新的方法和查询的方法类似，也是不断判断i和mid的关系，在左子树或者右子树递归更新，当找到该叶子节点时，更新它的sum，返回父节点也更新sum等于新的左右子树的sum的和。 完整代码如下： [cpp] class NumArray { private: struct Node { int start, end, sum; Node *left, *right; Node(int s, int e) :start(s), end(e), sum(0), left(NULL), right(NULL) {}; }; Node *root; Node* constructTree(vector<int> &nums, int start, int end) { Node* node = new Node(start, end); if (start == end) { node->sum = nums[start]; return node; } int mid = start + (end – start) / 2; node->left = constructTree(nums, start, mid); node->right = constructTree(nums, mid + 1, end); node->sum = node->left->sum + node->right->sum; return node; } int sumRange(int i, int j, Node *root) { if (root == NULL)return 0; if (i == root->start&&j == root->end)return root->sum; int mid = root->start + (root->end – root->start) / 2; if (j <= mid)return sumRange(i, j, root->left); else if (i > mid)return sumRange(i, j, root->right); else return sumRange(i, mid, root->left) + sumRange(mid + 1, j, root->right); } void update(int i, int val, Node *root) { if (root->start == root->end && root->start == i) { root->sum = val; return; } int mid = root->start + (root->end – root->start) / 2; if (i <= mid)update(i, val, root->left); else update(i, val, root->right); root->sum = root->left->sum + root->right->sum; } public: NumArray(vector<int> nums) { root = NULL; if (!nums.empty())root = constructTree(nums, 0, nums.size() – 1); } void update(int i, int val) { if (root == NULL)return; update(i, val, root); } int sumRange(int i, int j) { if (root == NULL)return 0; return sumRange(i, j, root); } }; [/cpp] 本代码提交AC，用时172MS。]]>