LeetCode Range Sum Query - Mutable

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的和。

完整代码如下:

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);
	}
};

本代码提交AC,用时172MS。

Leave a Reply

Your email address will not be published. Required fields are marked *