My new Java AC solution with heap, beat 50%, but potentially can be further optimized.


  • 0
    A

    The idea is to construct a heap with parent is the sum of two leaves, the root is bt[1] which hold the sum of the whole array. Use bt[1] as root. not bt[0], so we can calculate the parent index by

    parent_index = leaf_index >> 1
    

    to easily get the sum of all children.

    In this way, update a node only effect the path node from the leave to root, therefore it is O(logn)

    getting sum is little bit more tricky, it uses

    sum(i, j) = sum(0, j) - sum(0, i) + num[i];
    

    Here is the code.

    public class NumArray {
        int[] bt;
        int twoAlign;
    
        private int getLog2(int i) {
            int c = 0;
            while(i > (1 << c)) {
                c++;
            }
            return c;
        }
    
        public NumArray(int[] nums) {
            int len = nums.length;
            twoAlign = getLog2(len);
            bt = new int[1<<(twoAlign+1)];
            for (int i = 0; i < nums.length; i++) {
                bt[i+(1<<twoAlign)] = nums[i];
            }
            int c= twoAlign;
            while(c > 0) {
                c--;
                for (int i = 0; i < (1 << c); i++) {
                    bt[i+(1<<c)] = bt[2*(i+(1<<c))] +  bt[2*(i+(1<<c))+1];
                }
            }
        }
    
        void update(int i, int val) {
            int iChild = i+(1<<twoAlign);
            bt[iChild] = val;
            while((iChild >> 1) > 0) {
                iChild >>= 1;
                bt[iChild] = bt[iChild << 1] + bt[(iChild <<1)+1];
            }
        }
        
        private int sum0(int i) {
        	int sum0 = 0;
        	int c = 0;
        	i++;
        	while(i > 0) {
        		if ((i & (1 << c)) != 0) {
        			sum0 += bt[((1<<twoAlign) + i-1) >> c];
            		i -= (1 << c);
        		}
                c++;
        	}
        	return sum0;
        }
    
        public int sumRange(int i, int j) {
            return sum0(j) - sum0(i) + bt[i + (1<<twoAlign)];
        }
    }
    

Log in to reply
 

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