现在虽然还是不能很好的运用线段树以及使用起来还是会比较臃肿，但是早上看了会线段树今天也先给他总结一下
线段树是一种二叉树，是可以方便进行区间亦或者是单点维护以及查询一段区间之内的和
1 void build_tree(int node,int start,int end) 2 { 3 if(start==end) 4 { 5 tree[node]=arr[start]; 6 } 7 else 8 { 9 int mid=(start+end)/2; 10 int left_node=2*node; 11 int right_node=2*node+1; 12 build_tree(left_node,start,mid); 13 build_tree(right_node,mid+1,end); 14 tree[node]=tree[left_node]+tree[right_node]; 15 } 16 } 17 void update_tree(int node,int start,int end,int index,int val) 18 { 19 if(start==end) 20 { 21 arr[index]=arr[index]+val; 22 tree[node]+=val; 23 } 24 else 25 { 26 int mid=(start+end)/2; 27 int rnode=2*node+1; 28 int lnode=2*node; 29 if(index>=start&&index<=mid) 30 { 31 update_tree(lnode,start,mid,index,val); 32 } 33 else 34 { 35 update_tree(rnode,mid+1,end,index,val); 36 } 37 tree[node]=tree[lnode]+tree[rnode]; 38 } 39 } 40 int query_tree(int node,int start,int end,int L,int R) 41 { 42 if(R<start||L>end) 43 { 44 return 0; 45 } 46 else if(start==end) 47 { 48 return tree[node]; 49 } 50 else if(start>=L&&end<=R) 51 { 52 return tree[node]; 53 } 54 else 55 { 56 int mid=(start+end)/2; 57 int left_node=2*node; 58 int right_node=2*node+1; 59 int sum_left=query_tree(left_node,start,mid,L,R); 60 int sum_right=query_tree(right_node,mid+1,end,L,R); 61 return sum_left+sum_right; 62 } 63 }
对于上述代码的一些小小的理解，在构建线段树那里，对于树中的任意一个结点（不在递归出口时），这个结点的值应该是为它的左子节点和它的右子节点相加，而我需要求出每一个结点的值时，我则需要使用递归的方式一层一层下去，而递归的出口，就是当start==end的时候（这里的start和end指的是下面这个结点代表的区间），赋给这个结点一个原本的值，时间复杂度相对来说还是比较优秀有o(logn)
在数据更新那里（update）对于单个点来说，如果这个最终结点的值进行修改了的话，那么就要对其进行由下至上的一个大的修改，因此主要也还是通过递归来进行实现。其中start和end仍然表示其对应的区间。出口还是在末尾结点的时候
最后一段是区间查找并且返回相应的值，既然这样，那么查找的结果会有哪些呢？一个是找不到，也就是相应的start和end在这个区间外面的时候，返回的值是0，如果这个查找范围大于此时的区间结点区间范围亦或者是区间的start和end相同的时候，返回当时的结点值，如果再不是，那么就继续通过递归的方式去寻找最后找出答案
线段树还是属于一个知识点比较生涩的难以理解的，运用递归方式的一种算法，但是还是挺爽的（发现好像挺多人都会的就我不会，还是需要补一补的）
晚上继续摸，把区间给摸掉，加油！！！
原文：https://www.cnblogs.com/xyisreallycuteeee/p/14469841.html
