An AC 1724 ms C++ solution, used Binary Indexed Trees


  • 0

    ・What is "Binary Indexed Trees": http://blog.csdn.net/pi9nc/article/details/9006485

    ・The solution is really hard to explain, pls spend time on learning "Binary Indexed Trees".

    class NumArray 
    {
    private:
    	vector<int> n; //n used to copy input number array.
    	vector<int> tree; //tree[idx]=s[idx- 2^r + 1]+...+s[idx]; for example if idx=12=1100, there are two '0' after rightest '1', then r=2.
    	int sz;
    public:
    	NumArray(vector<int> &s) 
    	{
    		if (s.empty())
    			return;
    		n = s;
    		int idx, i, sum; //should note that idx started from 1, so if idx=2, it refer to the n[1].
    		sz = s.size(); 
    		vector<int> v(sz + 1, 0);
    		for (idx = 1; idx <= sz; ++idx)
    		{
    			sum = 0;
    			int one = -idx & idx; //-idx & idx used to calculate the value of last '1', for example, idx = 12= 1100, one = 100=4.
    			for (i = idx - one; i < idx; ++i)
    				sum += s[i];
    			v[idx] = sum;
    		}
    		tree = v;
    	}
    
    	void update(int i, int val) 
    	{
    		if (i < 0 || i >= sz)
    			return;
    		int dif = val - n[i];
    		n[i] = val;
    		int idx = i + 1;
    		for (; idx <= sz;)
    		{
    			tree[idx] += dif;
    			idx += -idx & idx;
    		}
    	}
    
    	int sumRange(int i, int j) 
    	{
    		if (i == j)
    			return n[i];
    		int a, b, idx;
    		a = b = 0;
    		for (idx = j + 1; idx;)
    		{
    			b += tree[idx];
    			idx -= -idx & idx;
    		}
    		if (0 == i)
    			return b;
    		for (idx = i; idx;)
    		{
    			a += tree[idx];
    			idx -= -idx & idx;
    		}
    		return b - a;
    	}
    };

Log in to reply
 

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