Binary indexed tree solution using C++


  • 0
    B
    class NumArray {
    public:
    vector<int> bitree;
    vector<int> nums;
    int n;
    
    NumArray(vector<int> &ns) {
    	nums = ns;
    	n = nums.size();
    	bitree.assign(n + 1, 0);
    	for (int i = 1; i <= n; i++) set(i, nums[i - 1]);
    }
    
    int bit(int x) {
    	return x & -x;
    }
    
    void update(int i, int val) {
    	int t = val - nums[i];
    	nums[i] = val;
    	set(i + 1, t);
    }
    
    void set(int i, int val) {
    	for (; i <= n; i += bit(i)) bitree[i] += val;
    }
    
    int get(int i) {
    	int ret = 0;
    	for (; i > 0; i -= bit(i)) ret += bitree[i];
    	return ret;
    }
    
    int sumRange(int i, int j) {
    	return get(j + 1) - get(i);
    }
    

    };


Log in to reply
 

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