## Wednesday, November 11, 2015

### LeetCode OJ - Range Sum Query - Immutable

Problem:

Solution:

Leveraging this formula, we can compute any range sum in $O(1)$ time given the running sums starting from 0.

$\sum\limits_{k = i}^{j} a_k = \sum\limits_{k = 0}^{j} a_k - \sum\limits_{k = 0}^{i - 1} a_k$

Code:

#include "stdafx.h"

// https://leetcode.com/problems/range-sum-query-immutable/

#include "LEET_RANGE_SUM_QUERY_IMMUTABLE.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_RANGE_SUM_QUERY_IMMUTABLE
{
class NumArray
{
public:
NumArray(vector<int> &nums)
{
int sum = 0;
runningSums.push_back(0);
for (unsigned int i = 0; i < nums.size(); i++)
{
sum += nums[i];
runningSums.push_back(sum);
}
}

int sumRange(int i, int j)
{
return runningSums[j + 1] - runningSums[i];
}
private:
vector<int> runningSums;
};
};

using namespace _LEET_RANGE_SUM_QUERY_IMMUTABLE;

int LEET_RANGE_SUM_QUERY_IMMUTABLE()
{
int case1[] = { -2, 0, 3, -5, 2, -1 };
vector<int> nums(case1, case1 + _countof(case1));
NumArray n(nums);
cout << n.sumRange(0, 2) << endl;
cout << n.sumRange(2, 5) << endl;
cout << n.sumRange(0, 5) << endl;
return 0;
}