本文共 2342 字，大约阅读时间需要 7 分钟。

线段树实例–灯笼哥大佬

import org.junit.Test;public class Test1 {
       //线段树实现query,update,build    @Test    public  void Test()//测试用例    {
           int[] tree = new int[15];        int[] array = {
   2,3,6,1,4,5};        build_tree(array,tree,0,array.length-1,0);        update(array,tree,0,5,0,4,10);        for (int i : tree) {
               System.out.print(i+" ");        }        System.out.println();        System.out.println(query(array,tree,0,array.length-1,0,0,5));    }    //array是原始数组,tree是用来存储线段树的数组,node_index是当前节点在tree中的索引    //start是当前节点对应区间的左边,end是当前节点的右边    //该函数的作用是将节点node_index及其子节点构建好    void build_tree(int[] array,int tree[],int start,int end,int node_index)    {
           if(start==end)        {
               tree[node_index] = array[start];        }        else        {
               int mid = (start+end)/2;            int left_node = 2*node_index+1;            int right_node = 2*node_index+2;            build_tree(array,tree,start,mid,left_node);            build_tree(array,tree,mid+1,end,right_node);            tree[node_index] = tree[left_node]+tree[right_node];        }    }    //该函数把索引为index的值改为val    void update(int[] array,int tree[],int start,int end,int node_index,int index,int val)    {
           if(start==end)        {
               tree[node_index] = val;            array[start] = val;        }        else        {
               int mid = (start+end)/2;            int left_node = 2*node_index+1;            int right_node = 2*node_index+2;            if(index<=mid)            {
                   update(array,tree,start,mid,left_node,index,val);            }            else            {
                   update(array,tree,mid+1,end,right_node,index,val);            }            tree[node_index]=tree[left_node]+tree[right_node];        }    }    //查询在特定区间内的和    int query(int[] array,int tree[],int start,int end,int node_index,int L,int R)//该函数实际执行的是中返回在L-R间的所有元素的和    {
           if(L>end||R
   
    =L)            return tree[node_index];        else        {
               int mid = (start+end)/2;            int left_node = 2*node_index+1;            int right_node = 2*node_index+2;            int sum_left = query(array,tree,start,mid,left_node,L,R);            int sum_right = query(array,tree,mid+1,end,right_node,L,R);            return sum_left+sum_right;        }    }}
   

转载地址：http://wplzi.baihongyu.com/