JAVA线段树模板

public class LineTree{

    int[] tree,nums;

    int n;

    public LineTree(int[] nums){

        this.nums = nums;

        n = nums.length;

        tree = new int[n*4];

        build(0, 0, n-1);

    }

    // 建立线段树

    private void build(int node, int left, int right){

        if(left == right){

            tree[node] = nums[left];

        }

        int mid = left + ((left + right)>> 1);

        build(2*node + 1, left, mid);

        build(2*node + 2, mid + 1, right);

        tree[node] = tree[2*node + 1] + tree[2*node + 2];

    }

    // 更新线段树

    public void update(int node, int left, int right, int idx, int val){

        if(left > right) return;

        else if(left == right){

            nums[left] = val;

            tree[node] = val;

        }else{

            int mid = left + ((left + right)>> 1);

            if(idx >= left && idx <= mid)

                update(node * 2 + 1, left, mid, idx, val);

            else

                update(node * 2 + 2, mid + 1, right, idx, val);

            tree[node] = tree[node*2 + 1] + tree[node*2 + 2];

        }

    }

    // 查询线段树

    public int query(int node, int left, int right, int L, int R){

        if(right < L || left > R) return 0;

        else if(left == right) return tree[node];

        else if(L<= left && R >= right)return tree[node];

        else{

            int mid = left + ((right - left) >> 1);

            return query(node*2+1, left, mid,L,R) + query(node*2+2, mid+1, right, L, R);

        }

    }

}
巴特西

JAVA线段树模板

最新文章

热门文章
