线段树---初体验

这两天做题遇到求叠加矩形的面积,需要利用到线段树,然后学习了下.
遇到两种使用场景,先记录下来,以后有时间再更深入了解下;

总体感悟: 线段树解决问题像是dp思想的一种延伸,用更高效的数据结构存储中间结果,便于更新和查询;

情况一:

区间更新,区间查询
题: #### 850. 矩形面积 II

/**
* 采用从底向上线性扫描;
* 线性扫描+离散化+线段树(带lazy)
**/

class Solution {
    public int[][] Tree;
    // 标示l到r+1点之间范围
    public void build(ArrayList<Integer> xValue,int p,int l,int r){
        if(l==r){
            Tree[p]= new int[]{0,xValue.get(r+1)-xValue.get(l)};
            return;
        }
        int mid = (l+r)/2;
        build(xValue,2*p,l,mid);
        build(xValue,2*p+1,mid+1,r);
        Tree[p]=new int[]{0,xValue.get(r+1)-xValue.get(l)};
    }
    // 由于有加有减,暂时没想好怎么处理cover ,先全扔在叶子节点上(全扔子节点又感觉浪费线段树了)
    public  void  add(int p,int l,int r,int x1,int x2,int cover){
        //if(x1<=l&&x2>=r&&l==r){  // 提高效率的话去掉ll==rr,想办法
        if(x1<=l&&x2>=r){  // 提高效率的话去掉ll==rr,想办法
            Tree[p][0]+=cover;
            return;
        }
        int mid= (l+r)/2;
        if(x1>mid){
            add(2*p+1,mid+1,r,x1,x2,cover);
            return;
        }
        if(x2<=mid){
            add(2*p,l,mid,x1,x2,cover);
            return;
        }
        add(2*p,l,mid,x1,mid,cover);
        add(2*p+1,mid+1,r,mid+1,x2,cover);
    }

    public int query(int p, int l, int r, int x1, int x2){
        if(x1>x2) return 0;
        //if(x1<=l&&x2>=r&&l==r){
        if(x1<=l&&x2>=r){            
            if(Tree[p][0]<0) return 0;
            if(Tree[p][0]>0) return Tree[p][1];
            if(l==r&&Tree[p][0]==0) return 0;
        }
        int mid=(l+r)/2;
        if(x1>mid) return query(2*p+1,mid+1,r,x1,x2);
        if(x2<=mid) return query(2*p,l,mid,x1,x2);
        return query(2*p,l,mid,x1,mid)+query(2*p+1,mid+1,r,mid+1,x2);
    }



    public int rectangleArea(int[][] rectangles) {
        // 用来存储由底往上的扫描线
        ArrayList<int[]> lines = new ArrayList<int[]>();
        // 存储所有x坐标个数();
        HashSet<Integer> X = new HashSet<Integer>();
        for(int[] arr:rectangles){
            // 底边-0:底边左端点x坐标,1:底边右端点坐标,2:底边高度,3:标识底边还是顶边
            int[] upLine = new int[]{arr[0],arr[2],arr[1],1};
            int[] downLine = new int[]{arr[0],arr[2],arr[3],-1};
            lines.add(upLine);
            lines.add(downLine);
            X.add(arr[0]);
            X.add(arr[2]);
        }
        // 按照底边的高度从低到高排序;
        lines.sort((int[] o1,int[] o2)->{
            return o1[2]-o2[2];
        });

        // 离散化
        ArrayList<Integer> xValue = new ArrayList<Integer>(X);
        xValue.sort((Integer o1,Integer o2)->{ return o1-o2;});
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        int index = 0;
        for(int x:xValue){
            map.put(x,index);
            index++;
        }
        // 构建线段树(这里暂时决定用数组表示树形结构),一共是map.size()-1段, 0-左index,1-右index,2:cover,3-sum;
        int size = map.size()-1;
        Tree = new int[4*size][2];
        // 初始化空Tree;
        build(xValue,1,0,size-1);

        long sum = 0;
        int pre = 0;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        // 底边-0:底边左端点x坐标,1:底边右端点坐标,2:底边高度,3:标识底边还是顶边
        for(int[] line:lines){
            if(line[2]==pre){
                int ll = map.get(line[0]);
                int rr = map.get(line[1])-1;
                add(1,0,size-1,ll,rr,line[3]);
                min=Math.min(ll,min);
                max=Math.max(rr,max);
                continue;
            }else if(line[2]>pre){
                int len = query(1,0,size-1,min,max);
                int height = line[2]-pre;
                sum+=(long)len*(long)height;
                sum=sum%((long)Math.pow(10,9)+7);

                pre = line[2];
                int ll = map.get(line[0]);
                int rr = map.get(line[1])-1;
                add(1,0,size-1,ll,rr,line[3]);
                min=Math.min(ll,min);
                max=Math.max(rr,max);
            }
        }
        return (int)(sum%((long)Math.pow(10,9)+7));
    }
}

情况二:

单点更新,区间查询:
题: 求最长递增子序列的个数;
这题也可以动态规划求,但是每次求dp[i]需要把dp[0]到dp[i-1]都更新一遍;
用线段树思想是不断的更新一张表,该表的每一项记录以某个值结尾的最长子序列的长度以及数量;

class Solution {
    // 核心思想:建立一个数组,维护从最小到最大值的线段树,每一段节点值包含长度和数量---表征现有序列中以x为最长子序列尾部数字时,最长子序列的长度和数量;(该题利用了线段树快速范围查询和单点修改的特性)
    // Tree[x][0]标示从0到p(l,r)范围内为子序列结尾的最长子序列长度len,Tree[x][1]标示最长子序列数量count
    public int[][] Tree;
    public void build(int p,int left,int right){
        // 这里情况特殊不需要像一般线段树那样进行递归初始化;
        for(int i=1;i<Tree.length;i++){
            Tree[i][1]=1;
        }
        // if(left>right) return;
        // if(left==right){
        //     Tree[p][0]=0;
        //     Tree[p][1]=1;
        //     return;
        // }
        // int mid = (left+right)/2;
        // build(2*p,left,mid);
        // build(2*p+1,mid+1,right);
        // Tree[p]=new int[]{0,1};
    }
    // 区间查询 0-left,0-left+1,...,0-right中最长的递增子序列
    public int[] query(int p,int l,int r,int left,int right){
        if(left>right) return new int[]{0,1};
        if(left<=l&&right>=r) return Tree[p];
        int mid = (l+r)/2;
        if(left>mid){
            return query(p<<1|1,mid+1,r,left,right);
        }
        if(right<=mid){
            return query(p<<1,l,mid,left,right);
        }
        int[] lResult = query(p<<1,l,mid,left, mid);
        int[] rResult = query(p<<1|1,mid+1,r,mid+1,right);
        // 左右长度一致的时候返回,该长度的数量为左右之和,否则为长的那个;
        if(lResult[0]==rResult[0]){
            int len=lResult[0];
            // 这里需要特殊考虑len=0时不要累加count
            if(len==0) return new int[]{0,1};
            int count=lResult[1]+rResult[1];
            return new int[]{len,count};
        }
        return lResult[0]>rResult[0]?lResult:rResult;
    }
    // 单点修改,更新树;
    public void update(int p,int l,int r,int index,int len,int count){
        // 找到位置就修改;
        if(l==r&&l==index){
            if(Tree[p][0]==len){
                Tree[p][1]+=count;
            }else{
                Tree[p][0]=len;
                Tree[p][1]=count;
            }
            return;
        }
        int mid = (l+r)/2;
        if(index>mid){
            update(p<<1|1,mid+1,r,index,len,count);
        }else{
            update(p<<1,l,mid,index,len,count);
        }
        if(Tree[p<<1|1][0]==Tree[p<<1][0]){
            Tree[p]=new int[]{Tree[p<<1][0],Tree[p<<1][1]+Tree[p<<1|1][1]};
            return;
        }
        Tree[p]=Tree[p<<1][0]>Tree[p<<1|1][0]?Tree[p<<1]:Tree[p<<1|1];
    }

    public int findNumberOfLIS(int[] nums) {
        if(nums==null||nums.length==0) return 0;

        // 对出现的数字进行离散化;(如果范围限定的小,数字比较均匀可以不需要离散化)
        HashSet<Integer> set = new HashSet<Integer>();
        for(int i:nums){
            set.add(i);
        }
        ArrayList<Integer> list = new ArrayList<Integer>(set);
        list.sort((Integer o1,Integer o2)->{return o1-o2;});
        int size = list.size();
        // 建立离散化后数值与脚标的索引;
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i=0;i<size;i++){
            map.put(list.get(i),i);
        }
        // 初始化线段树尺寸;
        Tree = new int[size*4][2];
        // 建立线段树
        build(1,0,size-1);
        // 单点更新线段树
        for(int i:nums){
            int index = map.get(i);
            int[] val = query(1,0,size-1,0,index-1);
            update(1,0,size-1,index,val[0]+1,val[1]);
        }
        return query(1,0,size-1,0, size-1)[1];
        
    }
}