Share my c++ solution: 1700ms, using tree array


  • 7
    Z
    class NumArray {
    public:
        NumArray(vector<int> &nums) {
            sz = nums.size();
            num = vector<int>(sz+1, 0);
            sum = vector<int>(sz+1, 0);
            for(int i=0; i<sz; i++) {
                update(i, nums[i]);
            }
            
        }
    
        void update(int idx, int val) {
            int oldv = num[idx+1];
            for(int i = idx+1; i<=sz; i+= (i&-i)) {
                sum[i] = sum[i] - oldv + val;
            }
            num[idx+1] = val;
        }
    
        int sumRange(int i, int j) {
            return getSum(j+1) - getSum(i);
        }
        
        int getSum(int idx) {
            int ret = 0;
            for(int i=idx; i>0; i-=(i&-i)) {
                ret += sum[i];
            }
            return ret;
        }
    private :
        int sz;
        vector<int> num;
        vector<int> sum;
    };
    

    log(n) to update, log(n) to sum


  • 0
    I

    Could you explain i&-i and why this is log(n)?


  • 0
    F

    This is a data structure called Binary Indexed Tree. It can be viewed as a degenerated segment tree.


  • 1
    Z

    i & -i get the right most 1 in the binary i;

    for example :i = 6

    00000110

    11111001 + 1 = 11111010

    6&-6 = 2;

    so that

    for(int i = idx+1; i<=sz; i+= (i&-i))

    in each iteration, i change the right most 1 to 0, so at most log(n) iterations.


  • 0
    J

    You are not using the tree at all....


Log in to reply
 

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