Short Java Segment Tree solution


  • -1
    J

    Based on http://codeforces.com/blog/entry/18051

    public class NumArray {
        int N;
        int[] st;
    
        public NumArray(int[] nums) {
            N = nums.length;
            st = new int[2 * N];
            for(int i = 0; i < N; i++) st[i + N] = nums[i];
            for(int i = N - 1; i > 0; i--) st[i] = st[i << 1] + st[i << 1 ^ 1];
        }
    
        void update(int i, int val) {
            for (st[i += N] = val; i > 1; i >>= 1) st[i >> 1] = st[i] + st[i ^ 1];
        }
    
        public int sumRange(int i, int j) {
            int res = 0;
            for (i += N, j += N + 1; i < j; i >>= 1, j >>= 1) {
                if ((i & 1) != 0) res += st[i++];
                if ((j & 1) != 0) res += st[--j];
            }
            return res;
        }
    }

Log in to reply
 

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