线段树入门：算法分析

算法分析

线段树采用了分而治之的策略，其点更新、区间更新、区间查询都可以在 时间内完成。树状数组和线段树都用于解决频繁修改和查询的问题，树状数组比线段树更节省空间、代码简单易懂，但是先单数用途更广、更加灵活，凡是可以使用树状数组的问题都可以用线段树来解决。

例题讲解

线段树的题目并不是一成不变的，对于不同的题目，你可能需要修改线段树的模板，来实现各种功能。

区域和检索-数组可修改

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

1. 其中一类查询要求更新数组nums下标对应的值
2. 另一类查询要求返回数组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

解题思路

本题是经典的线段树模板题，只需要根据之前的线段树模板稍作修改即可 （将区间最值查询改为区间求和）。

参考代码

class NumArray { public: struct sgntree{ int l,r,val; }T[120010]; vector<int>num; void build(int p,int l,int r){ T[p].l=l,T[p].r=r; if(l==r){ T[p].val=num[l-1]; return; } int mid=(l+r)>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); T[p].val=T[p<<1].val+T[p<<1|1].val; } NumArray(vector<int>& nums) { num=nums; int n=nums.size(); build(1,1,n); } void Update(int p,int l,int val){ if(T[p].l==T[p].r&&T[p].l==l){ T[p].val=val; return; } int mid=(T[p].l+T[p].r)>>1; if(l<=mid) Update(p<<1,l,val); else Update(p<<1|1,l,val); T[p].val=T[p<<1].val+T[p<<1|1].val; } void update(int index, int val) { Update(1,index+1,val); } int query(int p,int l,int r){ if(T[p].l>=l&&T[p].r<=r){ return T[p].val; } int mid=(T[p].l+T[p].r)>>1; if(r<=mid) return query(p<<1,l,r); if(l>mid) return query(p<<1|1,l,r); return query(p<<1,l,mid)+query(p<<1|1,mid+1,r); } int sumRange(int left, int right) { return query(1,left+1,right+1); } }; /** * Your NumArray object will be instantiated and called as such: * NumArray* obj = new NumArray(nums); * obj->update(index,val); * int param_2 = obj->sumRange(left,right); */