数据结构学习——线段树

ゝ一纸荒年。 2022-08-10 08:50 155阅读 0赞

> 线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
> 
> 1.  采用一维数组来存储线段树中的节点元素，所以必须要有一种数学关系将输入的元素（最底层叶子元素）对应到线段树的上层节点。
> 2.  自底向上建树。程序输入有m个数，这m其实就是线段树的叶子节点元素，但为了便于计算，将其扩大到2的幂，多出来的元素用不会影响程序的值的填充。
> 3.  在2的基础上自底向上建树，得到的就是一个满二叉树，而根据数学中等比数列和及其通项公式之间的关系：若第k层有n个元素，则前k-1层有n-1个元素。所以，存储整个线段树的数组空间大小应为（2\*n-1）。综合2、3，也就是有了常说的“线段树开4倍空间的说法”。  
>     4.最后一层有n个元素，其中前m个是程序输入的数据，最后一层之前的共有n-1个元素，所以若是从0开始编号的话，最后一层自左向右第一个元素的编号为n-1,这也就是在更新函数update中有”k += n-1;”这句话的原因。  
>     5.线段树在进行查询操作时，用query(a,b,0,0,n)，注意这里最后一个参数是n而不是m，因为在init操作中最后一层的元素已经由m变成了n个，区间编号0也应该对应\[0,n)

**线段树，根据节点中维护的数据的不同，线段树可以提供不同的功能。**

节点维护区间最小值，用线段树求区间最小值：

import java.util.Random;
    import java.util.Scanner;
    
    
    public class Main {
    
        public static int n;
        public static int[] nums;
    
        public static void init(int m){
            n = 1;
            while(n<m) n <<= 1;
            for(int i=0;i<2*n-1;i++) nums[i] = Integer.MAX_VALUE;
        }
    
        public static void update(int k,int v){
            k += n-1;//输入序列中的编号（最后一层）在一维数组中的下标对应
            nums[k] = v;
            while(k>0){
                k = (k-1)/2;
                nums[k] = Math.min(nums[k*2+1], nums[k*2+2]);
            }
        }
    
        //递归查询
        //[a,b)是待查询区间，[l,r)是当前所在区间，k为该区间的编号。
        public static int query(int a,int b,int k,int l,int r){
            if(a<=l&&r<=b) return nums[k];
            else if(l>=b||r<=a) return Integer.MAX_VALUE;
            else{
                int m = l+(r-l)/2;
                int left = query(a, b, l, m, k*2+1);
                int right = query(a, b, m, r, k*2+2);
                return Math.min(left, right);
            }
            //return Integer.MAX_VALUE;
        }
        public static void show(){
            System.out.println("nums:");
            for(int i=0;i<2*n-1;i++) System.out.print(nums[i]+" ");
            System.out.println();
        }
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner in = new Scanner(System.in);
            Random rand = new Random();
            while(in.hasNext()){
                int m = in.nextInt();
                nums = new int[m*4];
                init(m);
                int t;
                for(int i=0;i<m;i++){
                    t = in.nextInt();
                    update(i, t);
                }
                //show();
                //明确编号及其对应区间！
                int ans = query(0 , 5 , 0, 0 , n);
                System.out.println(ans);
            }
        }
    
    }

note：

> 1.满二叉树：每一层都是满的（拥有全部元素，对应二叉树的性质——第k层，最多有2^(k-1)个节点）。  
> 2.完全二叉树：**树中除了最后一层，其余层都是满的；而且最后一层或者是满的，或者是在右边缺少连续的若干接点，即若对节点编号的话，应与满二叉树相对应。**  
> 3.树中父子节点编号的值对应关系（不必刻意去记忆，由于是规律，届时只需要画出二叉树的前两层，即可使用了）：  
> son(n):  
> 当前节点编号为n，若树中节点编号是从0开始的，则其左子树根的节点编号为  
> 2\*n+1,右子树根的节点编号为2\*n+2 ; 若树中节点编号是从1开始的，若根节点为n，则其左子树根的节点编号为2\*n,右子树根的节点编号为2\*n+1。  
> parent(n):  
> 当前节点编号为n，若树中节点编号是从0开始的，则其父节点编号为（n-1)/2;若树中节点编号是从1开始的，则其父节点编号为n/2。

ps:程序中涉及到区间的时候，不论是STL、还是Java中的方法，采用的都是左闭右开区间。借鉴统一使用！