C++ 48ms simple log(n) solution


  • 0
    X
    class NumArray {
    public:
        vector<int> nums;
        vector<int> binaryIndexTree;
        int n;
        NumArray(vector<int> &nums) {
            this->nums = nums;
            this->n = nums.size();
            this->binaryIndexTree = vector<int>(nums.size() + 1, 0);
            for(int i = 1;i <= n; ++i){
                update(i);
            }
        }
        int sum(int p){
            int ans = 0;
            while(p > 0){
                ans += binaryIndexTree[p];
                p -= lowBit(p);
            }
            return ans;
        }
        void update(int p){
            int v = nums[p - 1];
            while(p <= n){
                binaryIndexTree[p] += v;
                p += lowBit(p);
            }
        }
        int lowBit(int i){
            return i & (-i);
        }
        int sumRange(int i, int j) {
            if(i > j){
                return 0;
            }
            return sum(j + 1) - sum(i + 1) + nums[i];
        }
    };

Log in to reply
 

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