算法计划

简介

树状数组

线段树

1. 例题
动态开点线段树

这题的数据范围太大了，开堆式线段树根本维护不了，所以可以直接动态开线段树，每次需要遍历子区间的时候才生成节点。

code

class CountIntervals {
    CountIntervals left, right;

    int l, r;
    int val;
    int mark;

    public CountIntervals() {
        this.l = 1;
        this.r = (int) 1e9;
    }

    public CountIntervals(int l, int r) {
        this.l = l;
        this.r = r;
    }

    public void add(int s, int t) {
        if (this.l > t || this.r < s) return;
        if(val == r-l+1)return;//没有这一行当重新遍历当前节点就会重新计算val
        if (this.l >= s && this.r <= t) {
            this.val = this.r - this.l + 1;
            return;
        } else {
            int mid = (this.l + this.r) >> 1;
            if (this.left == null) this.left = new CountIntervals(this.l, mid);
            if (this.right == null) this.right = new CountIntervals(mid + 1, this.r);
            this.left.add(s, t);
            this.right.add(s, t);
            
            this.val = this.left.val + this.right.val;
        }

    }

    public int count() {
        return this.val;
    }
}

摩尔投票+线段树维护可加区间

这题是个很有意思的题，要求查询区间的众数，我想了一下众数该怎么求但是想不出来该怎么维护那个区间信息。但是题目里有个很关键的点我第一时间没注意到，就是要求的阈值满足大于等于当前区间数一半以上。也就是说通过摩尔投票/打擂台的方式就可以在ON时间里吧众数求出来。但问题又来了，这个方法为什么能和线段树联系起来呢？因为摩尔投票其实是满足可加性的，可以这么想，将一个大区间分为两个子区间以后分别求众数分别为L1,L2，这时候求得数里一定有一个是大区间的众数设为L1，此时L2已经将它区间里的L1消耗完了，也就是说当L1-L2其实就是大区间求得的最后摩尔投票数。利用这个性质我们就可以维护所有区间的众数了。当然因为最后这个数里保存的投票数并非原本的投票数而是摩尔投票数，所以还需要用另一个map保存所有值的下标，然后通过二分查找，通过左右区间下标的index差求得这范围里一共多少个index即多少个众数。还需要验证是否满足阈值，否则返回-1。有点难写，因为java里没有二分，要手写两个二分，还要在维护区间的时候自定义一下摩尔投票的加法。

这题还有另一种做法，因为前面题干里说到满足摩尔投票的前置条件。所以当我们随机选取区间里的任意一个数选到众数的概率都是1/2，而我们对区间选取20次，如果左右如果没有出现阈值那么实际上存在阈值的可能性就几乎可以忽略不计了。而每一次随机选取验证方式就是上面那个算法统计count个数的方式。

code

class MajorityChecker {
    int []v;
    int []e;
    int []nums;
    List<Integer>[] map;
    int n;
    public int [] query1 (int left,int right,int s, int t,int p){
        if(left>=s&&right<=t){
            return new int[]{v[p],e[p]};
        }
        int mid = (left+right)>>1;
        if(mid>=t)return query1(left,mid,s,t,p<<1);
        if(mid<s)return query1(mid+1,right,s,t,p<<1|1);
        int[]subl = query1(left,mid,s,mid,p<<1),subr = query1(mid+1,right,mid+1,t,p<<1|1);
        if(subl[0]==subr[0]){
            return new int[]{subl[0],subl[1]+subr[1]};
        }else if(subl[1]>subr[1]){
            return new int[]{subl[0],subl[1]-subr[1]};
        }else return new int[]{subr[0],subr[1]-subl[1]};
    }
    public int binary_left(List<Integer> index,int left ,int right,int target){
        while(left<=right){
            int mid = left+right>>1;
            if(index.get(mid)<target){
                left = mid+1;
            }else{
                right = mid-1;
            }
        }
        return left;
    }
    public int binary_right(List<Integer> index,int left ,int right,int target){
        while(left<=right){
            int mid = (left+right)>>1;
            if(target<index.get(mid)){
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        return right;
    }
    public void build(int left,int right,int p){
        if(left == right){
            v[p] = nums[left];
            e[p] = 1;
            return ;
        }
        int mid = (left+right)>>1;
        build(left,mid,p<<1);
        build(mid+1,right,(p<<1)|1);
        if(v[p<<1]==v[(p<<1)|1]){
            v[p] = v[p<<1];
            e[p] = e[p<<1]+e[(p<<1)|1];
        }else if(e[p<<1]>e[p<<1|1]){
            v[p] = v[p<<1];
            e[p] = e[p<<1]-e[p<<1|1];
        }else{
            v[p] = v[p<<1|1];
            e[p] = e[p<<1|1]-e[p<<1];
        }
    }
    public MajorityChecker(int[] arr) {
        n = arr.length;
        nums = new int[n];
        map = new ArrayList[20005];
        Arrays.setAll(map, value -> new ArrayList<>());
        v = new int[n*4];e = new int[n*4];
        for(int i = 0 ; i < arr.length ; i ++){
            nums[i] = arr[i];
            map[arr[i]].add(i);
        }
        build(0,n-1,1);
    }

    public int query(int left, int right, int threshold) {
        int count = query1(0,n-1,left,right,1)[0];
        return (binary_right(map[count],0,map[count].size()-1,right)-binary_left(map[count],0,map[count].size()-1,left)+1>=threshold)?count:-1;
    }
}

DP+线段树维护区间最大值

这题比较有意思的地方就是把求LCS问题的第二层循环通过将值域用线段树统计并且查询，时间复杂度就降到了NLOGN而不是N^2。

code

class Solution {
    int [] v ;

    public int lengthOfLIS(int[] nums, int k) {
        int mx = 0;for(var t:nums)mx = Math.max(mx,t);
        v = new int[mx*4];
        for(int i = 0 ; i < nums.length ; i ++){
            if(nums[i]== 1)update(1,mx,1,1,1);
            else{
                int p = query(1,mx,nums[i]-k,nums[i]-1,1);
                update(1,mx,nums[i],p+1,1);
            }
        }
        return v[1];
    }
    int query(int l,int r,int s,int t ,int p){
        if(l>=s&&r<=t){
            return v[p];
        }
        int ans = 0;
        int mid = (l+r)>>1;
        if(mid>=s) ans = query(l,mid,s,t,p<<1);
        if(mid<t) ans = Math.max(ans,query(mid+1,r,s,t,p<<1|1));
        return ans;
    }
    void update(int l,int r,int x,int k,int p){
        if(l==r&&r==x){
            v[p] = Math.max(v[p],k);
            return ;
        }
        int mid = l+((r-l)>>1);
        if(mid>=x) update(l,mid,x,k,p<<1);
        if(mid<x)update(mid+1,r,x,k,p<<1|1);
        v[p] = Math.max(v[p<<1],v[p<<1|1]);
    }
}

DP+线段树维护区间最小值

这题我一眼看上去以为是个普通二维DP，但是实际上仔细看的话其实也是需要实现区间查询，单点更新/区间更新，单点查询的题。这两种方法可以根据你的遍历方式改变，居然有这种需求就可以直接用线段树维护。但值得注意的是，线段树维护的区间下标一定要和查询的保持一致，且尽量使用从1-n而不是0-n-1因为维护二维映射的时候太容易出错了。我就因为初始化起点的时候用(n-1)*(m-1)而不是n*m-1找了半个多小时。

code

class Solution {
    public int minimumVisitedCells(int[][] grid) {
        int n = grid.length;int m=grid[0].length;
        SegmentTree seg1 = new SegmentTree(m*n);
        SegmentTree seg2 = new SegmentTree(m*n);
        seg1.add(0,n*m-1,n*m-1,1,1);
        seg2.add(0,n*m-1,n*m-1,1,1);//必须用n*m-1，因为需要使用到这么多个数
        //if(n==1&&m==1)return 1;//由于是从后向前遍历，没法直接查询

        int k = 0x3f3f3f3f;
        for(int i = n-1 ; i >= 0 ; i --){
            for(int j = m-1 ;j >= 0 ; j --){
                //要注意映射规则i*m,j*n，然后两个树用不同的映射规则将横向或竖向的连续下标做保存。
                k = Math.min(seg1.query(0,m*n-1,i+j*n+1,j*n+Math.min(i+grid[i][j],n-1),1),seg2.query(0,m*n-1,i*m+j+1,i*m+Math.min(j+grid[i][j],m-1),1));
                seg1.add(0,n*m-1,j*n+i,k+1,1);
                seg2.add(0,n*m-1,i*m+j,k+1,1);
            }
        }
				k = Math.min(seg1.query(0,m*n-1,0,0,1),seg2.query(0,m*n-1,0,0,1));
        return k!=0x3f3f3f3f?k+1:-1;
    }
    class SegmentTree{
        int [] v ;
        int max = 0x3f3f3f3f;
        public SegmentTree(int n){
            v = new int[n*4];
            Arrays.fill(v,max);
        }
    int query(int l,int r,int s,int t ,int p){
        if(l>=s&&r<=t){
            return v[p];
        }
        int ans = max;
        int mid = (l+r)>>1;
        if(mid>=s) ans = Math.min(ans,query(l,mid,s,t,p<<1));
        if(mid<t) ans = Math.min(ans,query(mid+1,r,s,t,p<<1|1));
        return ans;
    }
    void add(int l,int r,int x,int k,int p){
        
        if(l==r&&r==x){
            v[p] = Math.min(v[p],k);
            return ;//一定要记得加return
        }
        int mid = l+((r-l)>>1);
        if(mid>=x) add(l,mid,x,k,p<<1);
        if(mid<x)add(mid+1,r,x,k,p<<1|1);
        v[p] = Math.min(v[p<<1],v[p<<1|1]);
    }
    }
    }

    //01 10 11 100 101 110 111
    //1  2  3  4   5   6   7   8

线段树维护01反转区间

这题是用线段树维护区间的一个典型例子，只需要区间维护1的数量，并且用一个lazy标签判断当前区间是否需要反转，就可以统计出来每个区间的1的数量了。

code

class Solution {
    class SegmentTree {
        public:
        int n;
        vector<long long>b;
        vector<int>*a;
        vector<bool>lazy;
        // vector<long long>sum;
    
        SegmentTree(int n,vector<int>&a) {
            this->n = n;
            b.resize(n*4);
            b.assign(n*4,0);
            lazy.resize(n*4);
            lazy.assign(n*4,false);
            // sum.resize(n*4);
            // sum.assign(n*4,0);
            this->a = &a;
            build(1,n,1);
        }
        void build(int s,int t,int p){
            if(s==t){
                b[p] = a->at(s-1);
                return;
            }
            int m = s+((t-s)>>1);
            build(s,m,p*2);
            build(m+1,t,p*2+1);
            pushup(p);
        }
        void pushup(int p){
                b[p] = b[p*2]+b[p*2+1];
        }
        void pushdown(int s,int t ,int p){
            if(lazy[p]){
                int m = s+((t-s)>>1);
                lazy[p*2] = !lazy[p*2];
                lazy[p*2+1] = !lazy[p*2+1];
                b[p*2] = (m-s+1)-b[2*p];
                b[p*2+1] = (t-m)-b[p*2+1];
                lazy[p] = false;
            }
        }
            //区间修改
        void update2(int left,int right,int s,int t,int p){
            if(s>right||t<left)return;
            if(s>=left&&t<=right){
                b[p] = (t-s+1)-b[p];
                lazy[p] = !lazy[p];
                return ;
            }
            int m = s+((t-s)>>1);
            pushdown(s,t,p);
            if(m>=left)update2(left,right,s,m,p*2);
            if(m<right)update2(left,right,m+1,t,p*2+1);
            pushup(p);
        }

        long long query1(){
                    //这段其实可以跳过，因为超过区间的值也不会返回0以外其他值
            return b[1];
        }
    };
public:
    vector<long long> handleQuery(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
        int n = nums1.size();
        SegmentTree st(n,nums1);
        long long sum = 0;
        for(int i=0;i<n;i++){
            sum += nums2[i];
        }
        int m = queries.size();
        vector<long long>ans;
        for(int i = 0 ; i < m ; i ++){
            int op = queries[i][0];
            if(op == 1){
                int l = queries[i][1],r = queries[i][2];
                st.update2(l+1,r+1,1,n,1);
                // cout<<st.query1()<<"!@!@"<<endl;
            }else if(op == 2){
                //cout<<st.query1()*queries[i][1]<<" "<<st.query1()<<endl;
                sum += st.query1()*queries[i][1];
            }else{
                ans.push_back(sum);
            }
        }
        return ans;
    }
};
//107
//101 
//011 /127 131 145/20 4 14
//010 001 /146/1
//110 111 000 /146/0
//011 /146/0

//109
//010000
//010010 001100 001010 /119 / 
//010110 /167 197