303. Range Sum Query

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note:

1. You may assume that the array does not change.

1. There are many calls to sumRange function.

维护一个数组，然后局部求和，典型的树状数组，或者使用线段树。

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <string>
using namespace std;

class NumArray {
public:
	NumArray(vector<int> &nums) 
	{
		n = nums.size();
		for (int i = 1; i <= n; i++)
		{
			num[i] = 0;
		}
		for (vector<int>::size_type i = 0; i < nums.size(); i++)
		{
			Update(i + 1, nums[i]);
		}
	}

	int sumRange(int i, int j) 
	{
		return Sum(j + 1) - Sum(i);
	}
private:
	int LowBit(int x)
	{
		return x & (-x);
	}
	int Sum(int end)
	{
		int sum = 0;
		while (end > 0)
		{
			sum += num[end];
			end -= LowBit(end);
		}
		return sum;
	}
	void Update(int pos, int value)
	{
		while (pos <= n)
		{
			num[pos] += value;
			pos += LowBit(pos);
		}
	}
	int num[1000000];
	int n;
};


int main()
{
	vector<int>vec{ -2, 0, 3, -5, 2, -1 };
	NumArray ss(vec);
	cout << ss.sumRange(0, 5);
	return 0;
}

num数组开的比较大

树状数组学习笔记：

http://blog.csdn.net/x_iya/article/details/8943264