我理解的数据结构（八）——线段树（SegmentTree）一、什么是线段树1、最经典的线段树问题：区间着色还有是一堵墙，长度为n。每次选择一段墙进行染色，经过m次操作，我们可以看到多少种颜色？经过m次操作，在区间[i,j]中我们可以看到多少种颜色？数据结构染色操作查询操作数组O(n)O(n)2.其他应用场景2017年注册用户中谁是最贵的用户？消费最少的用户？学习时间最长的用户？3.复杂度比较数据结构更新查询数组O(n)O(n)线段树O(logn)O(logn)4.线段树原理图以求和为例：2.线段树基础1.基本线线段树线段树不是完全二叉树。线段树是一棵平衡二叉树（整棵树的最大深度和最小深度的差值最大为1）。线段树仍然可以用数组表示。不存在的节点视为null，线段树为完全二叉树。2.数组存储线段树空间要求0层1层...h-1层12...2^(h-1)全二叉树：h层，共2^h-1个节点（约2^h)最后一层(h-1)层，有2^(h-1)个节点。最后一层的节点数大致等于前面所有层的节点数之和。如果需要存储n个元素n=2^k，只需要2n个空间n=2^k+1，需要4n个空间3、线段树基本代码publicclassSegmentTree{privateE[]data;私有E[]树；publicSegmentTree(E[]arr){data=(E[])newObject[arr.length];对于(inti=0;i=data.length){thrownewIllegalArgumentException("indexisillegal");}返回数据[索引];}//返回一个索引表示的元素在完全二叉树的数组表示中左子树的索引privateintleftChild(intindex){return2*index+1;}//返回索引所代表的元素在完全二叉树的数组表示中右子树的索引privateintrightChild(intindex){return2*index+2;}}四、创建线段树代码1.定义融合接口publicinterfaceMerge{//区间的元素如何定义由用户决定Emerge(Ea,Eb);}2.创建线段树代码privateMergemerge;publicSegmentTree(E[]arr,Mergemerge){//线段树的融合器，用于定义如何存储线段树的区间元素this.merge=合并；data=(E[])newObject[arr.length];对于(inti=0;i=data.length||queryR<0||queryR>=data.length){thrownewIllegalArgumentException("queryLorqueryRisillegal");}返回查询（0,0,data.length-1,queryL,queryR);}//递归,以treeIndex为根节点,区间为[l,r],查询区间为[queryL,queryR]privateEquery(inttreeIndex,intl,intr,intqueryL,intqueryR){if(l==queryL&&r==queryR){returntree[treeIndex];}intleftChildIndex=leftChild(treeIndex);intrightChildIndex=rightChild(treeIndex);intmid=(l+r)/2;如果(queryL>=mid+1){returnquery(rightChildIndex,mid+1,r,queryL,queryR);}elseif(queryR<=mid){returnquery(leftChildIndex,l,mid,queryL,queryR);}Eleft=query(leftChildIndex,l,mid,queryL,mid);Eright=query(rightChildIndex,mid+1,r,mid+1,queryR);返回合并。合并（左，右）；}、LeetCode第303题题目：303.面积与检索——数组不可变描述：给定一个整数数组nums，求数组中从索引i到j（i≤j）的元素之和，包括i和j观点示例：给定nums=[-2,0,3,-5,2,-1]，求和函数为sumRange()sumRange(0,2)->1sumRange(2,5)->-1sumRange(0,5)->-3解题代码：//注意如果要在leetcode上提交解法，必须同时提交Merge接口和SegmentTree类的代码，这里不是写NumArray类。公共类NumArray{私有SegmentTreesegTree;publicNumArray(int[]nums){if(nums.length>0){Integer[]data=newInteger[nums.length];对于(inti=0;i(data,(a,b)->a+b);}}publicintsumRange(inti,intj){if(segTree==null){thrownewIllegalArgumentException("segmenttreeisnull");}返回segTree.query(i,j);}}七、线段树更新publicvoidset(intindex,Ee){if(index<0||index>=data.length){thrownewIllegalArgumentException("indexisillegal");}set(0,0,data.length-1,index,e);}privatevoidset(inttreeIndex,intl,intr,intindex,Ee){if(l==r){tree[treeIndex]=e;返回;}intleftChildIndex=leftChild(treeIndex);intrightChildIndex=rightChild(treeIndex);intmid=(l+r)/2;if(index>=mid+1){set(rightChildIndex,mid+1,r,index,e);}elseif(index<=mid){set(leftChildIndex,l,mid,index,e);}tree[treeIndex]=merge.merge(tree[leftChildIndex],tree[rightChildIndex]);}8.LeetCode第307题：307.面积与检索-数组可修改描述：给定一个整数数组nums，求和从索引i到j(i≤j)的数组元素的数量，包括两点i和j例子：给定nums=[1,3,5]sumRange(0,2)->9update(1,2)sumRange(0,2)->8解题代码：classNumArray{//注意，如果你想要使用leetcode提交上面的答案，必须同时提交Merge接口和SegmentTree类的代码，这里不是写NumArray类中的privateSegmentTreesegTree；publicNumArray(int[]nums){if(nums.length>0){Integer[]data=newInteger[nums.length];对于(inti=0;i(data,(a,b)->a+b);}}publicvoidupdate(inti,intval){if(segTree==null){thrownewIllegalArgumentException("segmenttreeisnull");}segTree.set(i,val);}publicintsumRange(inti,intj){if(segTree==null){thrownewIllegalArgumentException("segmenttreeisnull");}返回segTree.query(i,j);}}
