RMQ 线段树 区间和、区间最值 代码

public class SegmentTree { @Test public void test(){ buildMin(0); int min = query(0, 3, 5); System.out.println(min); // updateOne(0,4,5); // max = query(0, 3, 5); // System.out.println(max);buildSum(0); } /**创建线段树（求和） */ int[] data = {5, 9, 7, 4, 6, 1};//数据 SegNode[] nodes = new SegNode[data.length << 2]; private void buildSum(int index){ SegNode node = nodes[index];//取出节点 if(node == null){//根节点 nodes[index] = new SegNode(0,data.length-1); node = nodes[index]; } if (node.start == node.end){//叶节点 node.val = data[node.start]; }else { int mid = (node.start + node.end) >> 1; int left = (index << 1) + 1; int right = left+1; nodes[left] = new SegNode(node.start,mid);//左子树 nodes[right] = new SegNode(mid+1,node.end);//右子树 buildSum(left);//递归 buildSum(right); node.val = nodes[left].val + nodes[right].val;//求和 } } /** * 创建线段树（最小值） */ private void buildMin(int index){ SegNode node = nodes[index];//取出节点 if(node == null){//根节点 nodes[index] = new SegNode(0,data.length-1); node = nodes[index]; } if (node.start == node.end){//叶节点 node.val = data[node.start]; }else{ int mid = (node.start + node.end) >> 1; int left = (index << 1) + 1; int right = left+1; nodes[left] = new SegNode(node.start,mid);//左子树 nodes[right] = new SegNode(mid+1,node.end);//右子树 buildMin(left);//递归 buildMin(right); node.val = Math.min(nodes[left].val, nodes[right].val);//最小值 } } /** * 区间查找 * @param index 起始索引下标 * @param start 区间左端点 * @param end 区间右端点 * @return 查找结构 */ private int query(int index,int start,int end){ SegNode node = nodes[index];//取出来 if(start <= node.start && node.end <= end)//如果在节点在查找区间内 return node.val; if (start > node.end || node.end < node.start){//区间之外 return Integer.MAX_VALUE;//没找到 }else{//部分在区间内 return Math.min(query((index << 1)+1,start,end),query((index << 1)+2,start,end));//最小值 // return query((index << 1)+1,start,end) + query((index << 1)+2,start,end);//求和 } } /** * 区间求和查找 * @param index 起始索引下标 * @param start 区间左端点 * @param end 区间右端点 * @return 查找求和结果 */ private int querySum(int index,int start,int end){ SegNode node = nodes[index];//取出来 if(start == node.start && node.end == end)//如果在节点在查找区间内 return node.val; if (start > node.end || node.end < node.start){//区间之外 return 0;//没找到 }else{//部分在区间内 int mid = (node.start + node.end) >> 1; return query((index << 1) + 1,start,mid < end ? mid : end) + query((index << 1) + 2,mid + 1 > start ? (mid+1) : start,end);//求和 } } /** * 求和，修改单点 * @param index * @param updateIndex * @param val * @return 区间单点修改，求和 */ private int updateForOneSum(int index,int updateIndex,int val){ SegNode node = nodes[index]; int remain; if(node.start == node.end && node.start == updateIndex){ remain = val - node.val; node.val = val; return remain; }else{ int mid = (node.start + node.end) >> 1; if(updateIndex <= mid){ remain = updateForOneSum((index << 1) + 1,updateIndex,val); }else{ remain = updateForOneSum((index << 1) + 2,updateIndex,val); } } node.val += remain; return remain; } /** * 最值，修改单点 * @param index * @param updateIndex * @param val * @return 区间单点修改，最值 */ private void updateForOne(int index,int updateIndex,int val){ SegNode node = nodes[index]; if(node.start == node.end && node.start == updateIndex){ node.val = val; }else{ int mid = (node.start + node.end) >> 1; int left = (index << 1) + 1; int right = left + 1; if(updateIndex <= mid){ updateForOneSum(left,updateIndex,val); }else{ updateForOneSum(right,updateIndex,val); } node.val = Math.min(nodes[left].val,nodes[right].val); } } /** * 线段树的数据结构 */ class SegNode{ int start; int end; int val; public SegNode(int s,int e){ start = s; end = e; } } }