题目

给你一个数组 nums ，请你完成两类查询。

其中一类查询要求 更新 数组 nums 下标对应的值
另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 ，其中 left <= right
实现 NumArray 类：

NumArray(int[] nums) 用整数数组 nums 初始化对象
void update(int index, int val) 将 nums[index] 的值 更新 为 val
int sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 （即，nums[left] + nums[left + 1], …, nums[right]）

示例 1：

输入：
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
输出：
[null, 9, null, 8]

解释：
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // 返回 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1,2,5]
numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8

提示：

1 <= nums.length <= 3 * 104
-100 <= nums[i] <= 100
0 <= index < nums.length
-100 <= val <= 100
0 <= left <= right < nums.length
调用 update 和 sumRange 方法次数不大于 3 * 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/range-sum-query-mutable
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析

我们先考虑一下暴力的方法，更新常数的时间复杂度，但是区间合要用O(n)的时间复杂度，想一种情况，当我们查询区间和的次数很多的时候，就造成了很多的重复计算，这里我们就用到了线段树，查询的时间复杂度降到了O(logn)

代码部分 模板部分 1.构造线段树

节点的值代表区间合，这里我们用数组代表线段树，第一个元素的左孩子是第二个元素，有孩子是第三个元素，以此类推，所以，第i个元素的左孩子是2i+1，右孩子是2i+2，根节点是整个区间的和，左孩子是左半部分，右孩子是右半部分，所以我们递归的来构造线段树

	//构造线段树 
	void bulid_segment_tree(vector<int> &value,vector<int> &nums,
	int pos,int left,int right)
	{
		//出口
		if(left==right)	//叶节点 
		{
			value[pos]=nums[left];
			return ; 
		}
		//现在能做的事情
		int mid=(left+right)/2;
		bulid_segment_tree(value,nums,pos*2+1,left,mid);
		bulid_segment_tree(value,nums,pos*2+2,mid+1,right);
		value[pos]=value[pos*2+1]+value[pos*2+2]; 
	}

2.线段树求区间和

一个区间的和相当于线段树的左边部分和区间重合的部分加上右边的，所以这里我们也递归的进行求解，当前区间在目标区间内时，我们直接返回当前节点的值，我之前有考虑过只要在区间内就返回值，这样会不会有重复的情况？但是我发现同一层的区间是永远不会重复，只有子树的区间跟根节点区间才会重复，我们返回值后就不会去遍历它的子树，问题自然就解决了。

	//线段树求和 
	int sum_segment_tree(vector<int> &value,int pos,
	int left,int right,int qleft,int qright)
	{
		//出口
		if(right<qleft||left>qright)
		{
			return 0;
		}
		if(left>=qleft&&right<=qright)
		{
			return value[pos];
		}		
		//现在能做的事情
 		int mid=(right+left)/2;
 		return sum_segment_tree(value,pos*2+1,left,mid,qleft,qright)+
 		sum_segment_tree(value,pos*2+2,mid+1,right,qleft,qright);
	}

3.线段树更新

跟上面几乎一样，我们要递归的深入去寻找目标节点，一定是一个叶子节点，但是我们更新完它后也要更新它所有的祖先，也就是一个回溯的过程

	//线段树更新
	void update_segment_tree(vector<int> &value,
	int pos,int left,int right,int index,int newvalue)
	{
		//出口
		if(left==right&&index==left)
		{
			value[pos]=newvalue;
			return ;
		}
		//现在能做的事情
		int mid=(left+right)/2;
		if(index<=mid)
		{
			update_segment_tree(value,pos*2+1,left,mid,index,newvalue);
		} 
		else
		{
			update_segment_tree(value,pos*2+2,mid+1,right,index,newvalue);
		}
		value[pos]=value[pos*2+1]+value[pos*2+2];
	}

完整代码

#include 
using namespace std;

class segment_tree
{
public:
	//构造线段树 
	void bulid_segment_tree(vector<int> &value,vector<int> &nums,
	int pos,int left,int right)
	{
		//出口
		if(left==right)	//叶节点 
		{
			value[pos]=nums[left];
			return ; 
		}
		//现在能做的事情
		int mid=(left+right)/2;
		bulid_segment_tree(value,nums,pos*2+1,left,mid);
		bulid_segment_tree(value,nums,pos*2+2,mid+1,right);
		value[pos]=value[pos*2+1]+value[pos*2+2]; 
	}
	
	//线段树求和 
	int sum_segment_tree(vector<int> &value,int pos,
	int left,int right,int qleft,int qright)
	{
		//出口
		if(right<qleft||left>qright)
		{
			return 0;
		}
		if(left>=qleft&&right<=qright)
		{
			return value[pos];
		}		
		//现在能做的事情
 		int mid=(right+left)/2;
 		return sum_segment_tree(value,pos*2+1,left,mid,qleft,qright)+
 		sum_segment_tree(value,pos*2+2,mid+1,right,qleft,qright);
	}
	
	//线段树更新
	void update_segment_tree(vector<int> &value,
	int pos,int left,int right,int index,int newvalue)
	{
		//出口
		if(left==right&&index==left)
		{
			value[pos]=newvalue;
			return ;
		}
		//现在能做的事情
		int mid=(left+right)/2;
		if(index<=mid)
		{
			update_segment_tree(value,pos*2+1,left,mid,index,newvalue);
		} 
		else
		{
			update_segment_tree(value,pos*2+2,mid+1,right,index,newvalue);
		}
		value[pos]=value[pos*2+1]+value[pos*2+2];
	}		
};

class NumArray {
public:
	vector<int> tree;
	int right_end;		//最右边元素的下标
	segment_tree s; 
	
    NumArray(vector<int>& nums) {
		for(int i=0;i<4*nums.size();i++)
			tree.push_back(0);
		right_end=nums.size()-1;
		s.bulid_segment_tree(tree,nums,0,0,right_end);
    }
    
    void update(int index, int val) {
		s.update_segment_tree(tree,0,0,right_end,index,val);
    }
    
    int sumRange(int left, int right) {
		return s.sum_segment_tree(tree,0,0,right_end,left,right);
    }
};

int main (void)
{
	vector<int> nums={1,3,5};
	NumArray s(nums);
	
	cout<<s.sumRange(0,2)<<endl;

	s.update(1,2);

	cout<<s.sumRange(0,2)<<endl;
	
	return 0;
}

总结

一道线段树的经典题，旨在提高对线段树具体实现的理解，这种模板都要做到倒背如流

May you succeed