[LeetCode]Range Sum Query - Mutable

Range Query的问题，有多重数据结构可以帮助我们解决。这里我们可以采用Sqrt Decomposition, Segment Tree或者Binary Index Tree来帮助我们查询和更新。具体的数据结构讲解和复杂度分析请参考对应的链接。

Sqrt Decompostio做法：

	class NumArray {
	public:
	NumArray(vector<int> nums) {
	n = nums.size();
	m_nums = nums;
	len = static_cast<int>(ceil(sqrt(n)));
	m_sq = vector<int>(len, 0);
	for(int i = 0; i < n; ++i)
	m_sq[i / len] += nums[i];
	}
	void update(int i, int val) {
	int diff = val - m_nums[i];
	m_nums[i] = val;
	m_sq[i / len] += diff;
	}
	int sumRange(int i, int j) {
	i = max(i, 0);
	j = min(j, n - 1);
	int startBlock = i / len, endBlock = j / len, sum = 0;
	if(startBlock == endBlock)
	{
	for(int k = i; k <= j; ++k)
	sum += m_nums[k];
	return sum;
	}
	for(int k = i; k < (startBlock + 1) * len; ++k)
	sum += m_nums[k];
	for(int k = startBlock + 1; k < endBlock; ++k)
	sum += m_sq[k];
	for(int k = endBlock * len; k <= j; ++k)
	sum += m_nums[k];
	return sum;
	}
	private:
	int n, len;
	vector<int> m_nums;
	vector<int> m_sq;
	};

view raw Range Sum Query - Mutable_III.cpp hosted with ❤ by GitHub

Segment Tree做法：

	class NumArray {
	public:
	NumArray(vector<int> nums) {
	n = nums.size();
	if(!n)return;
	m_st = vector<int>(3 * n, 0);
	createTree(0, n - 1, 0, nums);
	}
	void update(int i, int val) {
	updateTree(0, n - 1, i, 0, val);
	}
	int sumRange(int i, int j) {
	return query(i, j, 0, n - 1, 0);
	}
	private:
	vector<int> m_st;
	int n;
	void createTree(int lo, int hi, int i, vector<int>& nums)
	{
	if(lo == hi)
	{
	m_st[i] = nums[lo];
	return;
	}
	int mid = lo + (hi - lo) / 2;
	createTree(lo, mid, 2 * i + 1, nums);
	createTree(mid + 1, hi, 2 * i + 2, nums);
	m_st[i] = m_st[2 * i + 1] + m_st[2 * i + 2];
	}
	void updateTree(int lo, int hi, int target, int i, int val)
	{
	if(!n)return;
	if(lo == hi)
	{
	m_st[i] = val;
	return;
	}
	int mid = lo + (hi - lo) / 2;
	if(target <= mid)
	updateTree(lo, mid, target, 2 * i + 1, val);
	else
	updateTree(mid + 1, hi, target, 2 * i + 2, val);
	m_st[i] = m_st[2 * i + 1] + m_st[2 * i + 2];
	}
	int query(int qlo, int qhi, int lo, int hi, int i)
	{
	if(!n)return 0;
	int mid = lo + (hi - lo) / 2;
	if(qlo > hi || qhi < lo)
	return 0;
	else if(qlo <= lo && qhi >= hi)
	return m_st[i];
	else
	return query(qlo, qhi, lo, mid, 2 * i + 1) + query(qlo, qhi, mid + 1, hi, 2 * i + 2);
	}
	};
	/**
	* Your NumArray object will be instantiated and called as such:
	* NumArray obj = new NumArray(nums);
	* obj.update(i,val);
	* int param_2 = obj.sumRange(i,j);
	*/

view raw Range Sum Query - Mutable_I.cpp hosted with ❤ by GitHub

BIT做法：

	class NumArray {
	public:
	NumArray(vector<int> nums) {
	n = nums.size();
	if(!n)return;
	m_BIT = vector<int>(n + 1 , 0);
	m_nums = nums;
	for(int i = 0; i < n; ++i)
	add(i, nums[i]);
	}
	void update(int i, int val) {
	if(i < 0 || !n)return;
	int diff = val - m_nums[i];
	m_nums[i] = val;
	add(i, diff);
	}
	int sumRange(int i, int j) {
	return sumTo(j) - sumTo(i - 1);
	}
	private:
	vector<int> m_BIT;
	vector<int> m_nums;
	int n;
	int sumTo(int i)
	{
	++i;
	int sum = 0;
	while(i > 0)
	{
	sum += m_BIT[i];
	i -= i & -i;
	}
	return sum;
	}
	void add(int i, int val) {
	++i;
	while(i <= n)
	{
	m_BIT[i] += val;
	i += i & -i;
	}
	}
	};
	/**
	* Your NumArray object will be instantiated and called as such:
	* NumArray obj = new NumArray(nums);
	* obj.update(i,val);
	* int param_2 = obj.sumRange(i,j);
	*/

view raw Range Sum Query - Mutable_II.cpp hosted with ❤ by GitHub