线段树 区间和

线段树

package org.example.lc;

public class Test30 {
    static int[] tree;
    static int n;
    public static void main(String[] args) {
        int[] nums=new int[]{1,3,5};
        n=nums.length;
        tree=new int[n];
        build(0,0,n-1,nums);

    }

    public static void build(int node,int start,int end,int[] nums){
        if(start==end){
            tree[node]=nums[start];
            return;
        }
        int mid=(start+end)/2;
        build(node*2+1,start,mid,nums);
        build(node*2+2,mid+1,end,nums);
        tree[node]=tree[node*2+1]+tree[node*2+2];
    }

    public static void change(int index,int val,int node,int start,int end){
        if(start==end){
            tree[index]=val;
            return;
        }
        int mid=(start+end)/2;
        if(index<=mid){
            change(index,val,node*2+1,start,mid);
        }else{
            change(index,val,node*2+2,mid+1,end);
        }
        tree[node]=tree[node*2+1]+tree[node*2+2];
    }

    public static int range(int left,int right,int node,int start,int end){
        if(left==start&&right==end){
            return tree[node];
        }
        int mid=(start+end)/2;
        if(right<=mid){
            return range(left,right,node*2+1,start,mid);
        }else if(left>mid){
            return range(left,right,node*2+2,mid+1,end);
        }else{
            return range(left,mid,node*2+1,start,mid)+range(mid+1,right,node*2+2,mid+1,end);
        }
    }

}

线段树 维护区间的元素出现频率

线段树维护区间信息

class RangeFreqQuery{
    Map<Integer,Integer>[] tree;
    int n;
    public RangeFreqQuery(int[] arr){
        n=arr.length;
        tree=new HashMap[arr.length*4];
        for(int i=0;i<arr.length*4;i++){
            tree[i]=new HashMap<>();
        }
        build(arr,0,0,arr.length-1);
    }
    public void build(int[] arr,int node,int left,int right){
        if(left==right){
            tree[node].put(arr[left],tree[node].getOrDefault(arr[left],0)+1);
            return;
        }
        int mid=(left+right)/2;
        build(arr,node*2+1,left,mid);
        build(arr,node*2+2,mid+1,right);
        //合并
        Set<Map.Entry<Integer,Integer>> entries1=tree[node*2+1].entrySet();
        Set<Map.Entry<Integer,Integer>> entries2=tree[node*2+2].entrySet();
        for(Map.Entry<Integer,Integer> entry:entries1){
            int key=entry.getKey();
            int value=entry.getValue();
            tree[node].put(key,tree[node].getOrDefault(key,0)+value);
        }

        for(Map.Entry<Integer,Integer> entry:entries2){
            int key=entry.getKey();
            int value=entry.getValue();
            tree[node].put(key,tree[node].getOrDefault(key,0)+value);
        }

    }

    public int ask(int l,int r,int value,int node,int left,int right){
        if(l==left&&r==right){
            return tree[node].getOrDefault(value,0);
        }
        int mid=(left+right)/2;
        if(r<=mid){
            return ask(l,r,value,node*2+1,left,mid);
        }else if(l>mid){
            return ask(l,r,value,node*2+2,mid+1,right);
        }else{
            return ask(l,mid,value,node*2+1,left,mid)+ask(mid+1,r,value,node*2+2,mid+1,right);
        }
    }

    public int query(int left,int right,int value){
        return ask(left,right,value,0,0,n-1);
    }
}

/**
 * Your RangeFreqQuery object will be instantiated and called as such:
 * RangeFreqQuery obj = new RangeFreqQuery(arr);
 * int param_1 = obj.query(left,right,value);
 */