Concise Segment Tree Solution


  • 0
    N

    '''
    class Solution{
    int n;
    int[] tree;
    public NumArray(int[] nums) {
    n = nums.length+(nums.length&1);
    tree = new int[n*2+1];
    for(int i = 0;i<nums.length;i++)
    tree[i+n]=nums[i];
    build();

    }
    
    public void build(){
        for(int i = n-1;i>0;i--)
            tree[i]=tree[i<<1]+tree[i<<1|1];
    }
    
    public void update(int p, int value) {
     
        for (tree[p += n] = value; p > 1; p >>= 1) tree[p>>1] = tree[p] + tree[p^1];
     
    }
    
    public int sumRange(int i, int j) {
         int res = 0;
          for (i += n, j += n; i <= j; i >>= 1, j >>= 1) {
            if ((i&1)==1) res += tree[i++];
            if ((j&1)==0) res += tree[j--];
          }
          return res;
    }
    

    }
    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.