Solving Range Sum Query - Mutable
class NumArray {
public:
NumArray(vector<int> nums) {
Image.push_back(vector<int>(nums));
int size = nums.size();
int level = 1;
while(size >= 10)
{
Image.push_back(vector<int>(size/10, 0));
for(int i = 0; i < size/10; i++)
{
int localSum = 0;
for(int j = 0; j < 10; j++)
localSum += Image[level-1][10*i+j];
Image[level][i] = localSum;
}
size /= 10;
level += 1;
}
}
void update(int i, int val) {
int diff = val - Image[0][i];
Image[0][i] = val;
for(int level = 1; level < Image.size(); level++)
{
i /= 10;
Image[level][i] += diff;
}
}
int sumRange(int i, int j) {
if(i == j)
return Image[0][i];
int sum = Image[0][j];
int level = 0;
while(true)
{
while(i % 10 != 0 && i != j)
{
sum += Image[level][i];
i++;
}
while(j % 10 != 0 && j != i)
{
j--;
sum += Image[level][j];
}
// escape condition
if(i == j)
{
break;
}
level++;
i /= 10;
j /= 10;
}
return sum;
}
private:
vector<vector<int>> Image;
};
public:
NumArray(vector<int> nums) {
Image.push_back(vector<int>(nums));
int size = nums.size();
int level = 1;
while(size >= 10)
{
Image.push_back(vector<int>(size/10, 0));
for(int i = 0; i < size/10; i++)
{
int localSum = 0;
for(int j = 0; j < 10; j++)
localSum += Image[level-1][10*i+j];
Image[level][i] = localSum;
}
size /= 10;
level += 1;
}
}
void update(int i, int val) {
int diff = val - Image[0][i];
Image[0][i] = val;
for(int level = 1; level < Image.size(); level++)
{
i /= 10;
Image[level][i] += diff;
}
}
int sumRange(int i, int j) {
if(i == j)
return Image[0][i];
int sum = Image[0][j];
int level = 0;
while(true)
{
while(i % 10 != 0 && i != j)
{
sum += Image[level][i];
i++;
}
while(j % 10 != 0 && j != i)
{
j--;
sum += Image[level][j];
}
// escape condition
if(i == j)
{
break;
}
level++;
i /= 10;
j /= 10;
}
return sum;
}
private:
vector<vector<int>> Image;
};
留言
張貼留言