Description

  1. Segment tree: update one element & query for intervals

  2. Segment tree: update intervals & query one element

    • the lazy update operations are very important to improve the efficience
    • so, PushDown means pushing the laziness down to its’ sub-trees

Code

  1. // https://leetcode.com/problems/range-sum-query-mutable/
class NumArray {
class ST{
    int l, r, val;
    public ST(int l, int r, int v){
        this.l = l;
        this.r = r;
        this.val = v;
    }
}
    
ST[] st;
    
private int Left(int x) {
    return 2 * x + 1;
}
private int Right(int x) {
    return 2 * x + 2;
}
        
private void build(ST[] st, int stIndex, int[] nums, int l, int r){
    if(l == r){
        st[stIndex] = new ST(l, r, nums[l]);
        return ;
    }
    int mid = (r - l) / 2 + l;
    build(st, Left(stIndex), nums, l, mid);
    build(st, Right(stIndex), nums, mid + 1, r);
    st[stIndex] = new ST(l, r, st[Left(stIndex)].val + st[Right(stIndex)].val);
}
    
private void updateST(int targetIndex, int newValue, ST[] st, int stIndex){
    if(st[stIndex].l == st[stIndex].r && st[stIndex].l == targetIndex){
        st[stIndex].val = newValue;
        return ;
    }
    int mid = (st[stIndex].r - st[stIndex].l) / 2 + st[stIndex].l;
    if(targetIndex >= st[stIndex].l && targetIndex <= mid){
        updateST(targetIndex, newValue, st, Left(stIndex));
    }
    else {
        updateST(targetIndex, newValue, st, Right(stIndex));
    }
    st[stIndex] = new ST(st[stIndex].l, st[stIndex].r, st[Left(stIndex)].val + st[Right(stIndex)].val);
}
    
private int query(int targetLeft, int targetRight, ST[] st, int stIndex){
    if(targetLeft == st[stIndex].l && targetRight == st[stIndex].r){
        return st[stIndex].val;
    }
    int mid = (st[stIndex].r - st[stIndex].l) /2 + st[stIndex].l;
    if(targetLeft > mid){
        return query(targetLeft, targetRight, st, Right(stIndex));
    }
    else if(targetRight <= mid){
        return query(targetLeft, targetRight, st, Left(stIndex));
    }
    else return query(targetLeft, mid, st, Left(stIndex)) + query(mid + 1, targetRight, st, Right(stIndex));
}

public NumArray(int[] nums) {
    if(nums.length > 0){
        st = new ST[nums.length << 2];
        build(st, 0, nums, 0, nums.length - 1);
    }
}
    
public void update(int i, int val) {
    updateST(i, val, st, 0);
}
    
public int sumRange(int i, int j) {
    return query(i, j, st, 0);
}
}

    2.

    //https://leetcode.com/problems/my-calendar-iii/
class MyCalendarThree {
    
class TreeNode{
    int l, r, max, lazy;
    TreeNode left, right;
    public TreeNode(int l, int r, int val){
        this.l = l;
        this.r = r;
        this.max = val;
        this.lazy = 0;
    }
}
    
TreeNode root;
    
public MyCalendarThree() {
    root = new TreeNode(0, 1000000000, 0);
}
    
private void update(TreeNode rt, int targetLeft, int targetRight){
    if(rt.l == targetLeft && rt.r == targetRight){
        rt.lazy ++;
        rt.max ++;
        return;
    }
    if(rt.l == rt.r) return ;
        
    int mid = (rt.r - rt.l) / 2 + rt.l;
    if(rt.left == null){
        rt.left = new TreeNode(rt.l, mid, 0);
    }
    if(rt.right == null){
        rt.right = new TreeNode(mid + 1, rt.r, 0);
    }
        
    // push down
    if(rt.lazy > 0){
        rt.left.lazy += rt.lazy;
        rt.left.max += rt.lazy;
        rt.right.lazy += rt.lazy;
        rt.right.max += rt.lazy;
        rt.lazy = 0;
    }
        
    if(mid >= targetRight) update(rt.left, targetLeft, targetRight);
    else if(mid < targetLeft) update(rt.right, targetLeft, targetRight);
    else {
        update(rt.left, targetLeft, mid);
        update(rt.right, mid + 1, targetRight);
    }
        
    // push up
    rt.max = Math.max(rt.right.max, rt.left.max);
}
    
public int book(int start, int end) {
    update(root, start, end - 1);
    return root.max;
}
}