C++ 52ms Binary Indexed Tree


  • 0
    C
    class NumArray {
    public:
    NumArray(vector<int> &nums) {
    	int n = nums.size();
    
    	vc.resize(n);
    	len = n;
    	array.resize(n + 1);
    
    	for (int i = 0; i < n; i++)
    		update(i, nums[i]);
    	vc = nums;
    }
    
    void update(int i, int val) {
    	
    	int diff = val - vc[i];
    	vc[i] = val;
    	i = i + 1;
    	while (i <= len)
    	{
    		array[i] += diff;
    		i += lowbit(i);
    	}
    }
    
    int sumRange(int i, int j) {
    	int to = 0, to1 = 0;
    	int n = i , m = j + 1;
    	while (n > 0)
    	{
    		to += array[n];
    		n -= lowbit(n);
    	}
    	while (m > 0)
    	{
    		to1 += array[m];
    		m -= lowbit(m);
    	}
    	//cout << to1 - to << endl;
    	return to1 - to;
    }
    
    private:
    vector<int> vc;
    vector<int> array;
    int len;
    int lowbit(int x)
    {
    	return x&(-x);
    }
    };

Log in to reply
 

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