线段树入门：算法分析

算法分析线段树采用了分而治之的策略其点更新、区间更新、区间查询都可以在 时间内完成。树状数组和线段树都用于解决频繁修改和查询的问题树状数组比线段树更节省空间、代码简单易懂但是先单数用途更广、更加灵活凡是可以使用树状数组的问题都可以用线段树来解决。例题讲解线段树的题目并不是一成不变的对于不同的题目你可能需要修改线段树的模板来实现各种功能。区域和检索-数组可修改给你一个数组nums请你完成两类查询。其中一类查询要求更新数组nums下标对应的值另一类查询要求返回数组nums中索引left和索引right之间包含的nums元素的和其中left right实现NumArray类NumArray(int[] nums)用整数数组nums初始化对象void update(int index, int val)将nums[index]的值更新为valint 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 9numArray.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]; vectorintnum; void build(int p,int l,int r){ T[p].ll,T[p].rr; if(lr){ T[p].valnum[l-1]; return; } int mid(lr)1; build(p1,l,mid); build(p1|1,mid1,r); T[p].valT[p1].valT[p1|1].val; } NumArray(vectorint nums) { numnums; int nnums.size(); build(1,1,n); } void Update(int p,int l,int val){ if(T[p].lT[p].rT[p].ll){ T[p].valval; return; } int mid(T[p].lT[p].r)1; if(lmid) Update(p1,l,val); else Update(p1|1,l,val); T[p].valT[p1].valT[p1|1].val; } void update(int index, int val) { Update(1,index1,val); } int query(int p,int l,int r){ if(T[p].llT[p].rr){ return T[p].val; } int mid(T[p].lT[p].r)1; if(rmid) return query(p1,l,r); if(lmid) return query(p1|1,l,r); return query(p1,l,mid)query(p1|1,mid1,r); } int sumRange(int left, int right) { return query(1,left1,right1); } }; /** * 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); */