Simple c++ solution beat 100.00%, using Binary Index Tree


  • 1
    I

    Actually we can solve this problem simply by using an array storing the sums of first i elements instead of using Binary Index Tree. If you don't know Binary Index Tree, you can find it easily on the internet. If we use Binary Index Tree, we can easily extend it to solve the mutable version of this problem.

    vector<int> BIT;
    
    NumArray(vector<int> &nums) {
        BIT.resize(nums.size() + 1, 0);
        for (int i = 0; i < nums.size(); i++) BIT[i + 1] = nums[i];
        int gap = 2;
        while (gap < BIT.size()) {
            for (int i = gap; i < BIT.size(); i += gap) BIT[i] += BIT[i - gap / 2];
            gap *= 2;
        }
    }
    
    int getSum(int i) {
        int ret = 0;
        while (i) {
            ret += BIT[i];
            i &= (i - 1);
        }
        return ret;
    }
    
    int sumRange(int i, int j) {
        return getSum(j + 1) - getSum(i);
    }

  • 0
    W

    si guo yi, what a brilliant solution


Log in to reply
 

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