leetcodeノート:Range Sum Query-Mutable
一.タイトルの説明
Given an integer array
The
Example: Given
Note: The array is only modifiable by the update function. You may assume the number of calls to update and sumRange function is distributed evenly.
二.テーマ分析
問題はRange Sum Query-Immutableの問題に基づいて増加する難易度であり,配列numsを入力すると配列の要素を修正でき,毎回1つの要素しか修正できないことが要求される.同様に配列のある区間和を求める機能を実現する.
次の場合http://blog.csdn.net/liyuefeilong/article/details/505516621つの問題のやり方を少し改善すると、機能を実現できますが、タイムアウトします.
この時、いくつかの文章を読んでから、元の古典的なやり方(前の問題を含む)は木状の配列を使ってこの配列numsを維持することであり、その挿入とクエリーはO(logn)の複雑さを実現することができ、非常に巧みであることが分かった.
ツリー配列については、以下のブログでよく説明しています.
http://blog.csdn.net/int64ago/article/details/7429868
三.サンプルコード
四.小結
前に聞いたことがあるだけで、これは初めて木の配列を使って、これは配列を維持する1つのとても良い思想で、深く学ぶ必要があります!
Given an integer array
nums
, find the sum of the elements between indices i
and j
(i ≤ j)
, inclusive. The
update(i, val)
function modifies nums
by updating the element at index i
to val
. Example: Given
nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
Note: The array is only modifiable by the update function. You may assume the number of calls to update and sumRange function is distributed evenly.
二.テーマ分析
問題はRange Sum Query-Immutableの問題に基づいて増加する難易度であり,配列numsを入力すると配列の要素を修正でき,毎回1つの要素しか修正できないことが要求される.同様に配列のある区間和を求める機能を実現する.
次の場合http://blog.csdn.net/liyuefeilong/article/details/505516621つの問題のやり方を少し改善すると、機能を実現できますが、タイムアウトします.
この時、いくつかの文章を読んでから、元の古典的なやり方(前の問題を含む)は木状の配列を使ってこの配列numsを維持することであり、その挿入とクエリーはO(logn)の複雑さを実現することができ、非常に巧みであることが分かった.
ツリー配列については、以下のブログでよく説明しています.
http://blog.csdn.net/int64ago/article/details/7429868
三.サンプルコード
//
class NumArray {
public:
NumArray(vector<int> &nums) {
if (nums.empty()) return;
else
{
sums.push_back(nums[0]);
//
int len = nums.size();
for (int i = 1; i < len; ++i)
sums.push_back(sums[i - 1] + nums[i]);
}
}
void update(int i, int val) {
for (int k = i; k < nums.size(); ++k)
sums[k] += (val - nums[i]);
nums[i] = val;
}
int sumRange(int i, int j) {
return sums[j] - sums[i - 1];
}
private:
vector<int> nums;
//
vector<int> sums;
};
// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);
// AC, O(logn)
class NumArray {
private:
vector<int> c;
vector<int> m_nums;
public:
NumArray(vector<int> &nums) {
c.resize(nums.size() + 1);
m_nums = nums;
for (int i = 0; i < nums.size(); i++){
add(i + 1, nums[i]);
}
}
int lowbit(int pos){
return pos&(-pos);
}
void add(int pos, int value){
while (pos < c.size()){
c[pos] += value;
pos += lowbit(pos);
}
}
int sum(int pos){
int res = 0;
while (pos > 0){
res += c[pos];
pos -= lowbit(pos);
}
return res;
}
void update(int i, int val) {
int ori = m_nums[i];
int delta = val - ori;
m_nums[i] = val;
add(i + 1, delta);
}
int sumRange(int i, int j) {
return sum(j + 1) - sum(i);
}
};
// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);
四.小結
前に聞いたことがあるだけで、これは初めて木の配列を使って、これは配列を維持する1つのとても良い思想で、深く学ぶ必要があります!