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
- Method 1: 通过数组存储数据。
class NumArray {
private int[] nums;
public NumArray(int[] nums) {
this.nums = nums;
}
public void update(int i, int val) {
nums[i] = val;
}
public int sumRange(int i, int j) {
int sum = 0;
for(; i <= j; i++)
sum += this.nums[i];
return sum;
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* obj.update(i,val);
* int param_2 = obj.sumRange(i,j);
*/- Method 2: 保存从0加到当前数的和
class NumArray {
private int[] sum;
public NumArray(int[] nums) {
this.sum = new int[nums.length];
int count = 0;
for(int i = 0; i < nums.length; i++){
count += nums[i];
sum[i] = count;
}
}
public void update(int i, int val) {
int old = i > 0? (sum[i] - sum[i - 1]): sum[0];
int diff = val - old;
for(int j = i; j < sum.length; j++){
sum[j] += diff;
}
}
public int sumRange(int i, int j) {
if(i == 0) return sum[j];
else
return sum[j] - sum[i - 1];
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* obj.update(i,val);
* int param_2 = obj.sumRange(i,j);
*/- Use binary index tree
class NumArray {
private int[] c;
private int[] nums;
private int lowBit(int n){
return n & (-n);
}
public NumArray(int[] nums) {
c = new int[nums.length + 1];
this.nums = nums;
for(int i = 1; i <= nums.length; i++){
int lowBit = lowBit(i);
int sum = 0;
for(int j = i - lowBit + 1; j <= i; j++){
sum += nums[j - 1];
}
c[i] = sum;
}
}
public void update(int i, int val) {
int diff = val - nums[i];
nums[i] = val;
int index = i + 1;
while(index <= this.nums.length){
c[index] += diff;
index += lowBit(index);
}
}
public int sumRange(int i, int j) {
int sum1 = 0;
int index1 = i;
while(index1 > 0){
sum1 += c[index1];
index1 -= lowBit(index1);
}
int sum2 = 0;
int index2 = j + 1;
while(index2 > 0){
sum2 += c[index2];
index2 -= lowBit(index2);
}
return sum2 - sum1;
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* obj.update(i,val);
* int param_2 = obj.sumRange(i,j);
*/- Use segment tree to solve this question.
class NumArray {
private int[] segment;
private int[] nums;
public NumArray(int[] nums) {
this.segment = new int[nums.length << 2 + 1];
this.nums = nums;
if(nums != null && nums.length != 0) build(1, nums.length, 1);
}
private void build(int l, int r, int k){
if(l == r){
segment[k] = this.nums[l - 1];
}else{
int m = l + ((r - l) >> 1);
build(l, m, k << 1);
build(m + 1, r, k << 1 | 1);
segment[k] = segment[k << 1] + segment[k << 1 | 1];
}
}
public void update(int i, int val) {
update(i + 1, val - this.nums[i], 1, this.nums.length, 1);
this.nums[i] = val;
}
private void update(int i, int diff, int l, int r, int k){
if(l == r) segment[k] += diff;
else{
int mid = l + ((r - l) >> 1);
if(i <= mid) update(i, diff, l, mid, k << 1);
else update(i, diff, mid + 1, r, k << 1 | 1);
segment[k] = segment[k << 1] + segment[k << 1 | 1];
}
}
public int sumRange(int i, int j) {
return sum(i + 1, j + 1, 1, this.nums.length, 1);
}
private int sum(int L, int R, int l, int r, int k){
if(L <= l && R >= r) return segment[k];
else{
int m = l + ((r - l) >> 1);
int sum = 0;
if(L <= m) sum += sum(L, R, l, m, k << 1);
if(R > m) sum += sum(L, R, m + 1, r, k << 1 | 1);
return sum;
}
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* obj.update(i,val);
* int param_2 = obj.sumRange(i,j);
*/- BIT
class NumArray {
private int[] nums;
private int[] bit;
private int lowBit(int x){
return x & (-x);
}
public NumArray(int[] nums) {
this.nums = new int[nums.length + 1];
for(int i = 0; i < nums.length; i++){
this.nums[i + 1] = nums[i];
}
this.bit = new int[nums.length + 1];
for(int i = 1; i < this.nums.length; i++){
for(int j = i - lowBit(i) + 1; j <= i; j++)
this.bit[i] += this.nums[j];
}
}
public void update(int i, int val) {
int diff = val - nums[i + 1];
nums[i + 1] = val;
int index = i + 1;
while(index < nums.length){
bit[index] += diff;
index += lowBit(index);
}
}
private int sum(int i){
int sum = 0;
while(i > 0){
sum += bit[i];
i -= lowBit(i);
}
return sum;
}
public int sumRange(int i, int j) {
return sum(j + 1) - sum(i);
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* obj.update(i,val);
* int param_2 = obj.sumRange(i,j);
*/- Segment Tree
class NumArray {
private int[] nums;
private int[] segment;
public NumArray(int[] nums) {
if(nums == null || nums.length == 0) return;
this.nums = nums;
this.segment = new int[nums.length << 2 + 1];
insert(1, nums.length, 1);
}
private void insert(int l, int r, int k){
if(l == r) segment[k] = nums[l - 1];
else{
int m = l + ((r - l) >> 1);
insert(l, m, k << 1);
insert(m + 1, r, k << 1 | 1);
segment[k] = segment[k << 1] + segment[k << 1 | 1];
}
}
public void update(int i, int val) {
update(i, val - nums[i], 1, nums.length, 1);
this.nums[i] = val;
}
private void update(int i, int diff, int l, int r, int k){
if(l == r) segment[k] += diff;
else{
int m = l + ((r - l) >> 1);
if((i + 1) <= m) update(i, diff, l, m, k << 1);
if((i + 1) > m) update(i , diff, m + 1, r, k << 1 | 1);
segment[k] = segment[k << 1] + segment[k << 1 | 1];
}
}
public int sumRange(int i, int j) {
return sumRange(i + 1, j + 1, 1, this.nums.length, 1);
}
private int sumRange(int L, int R, int l, int r, int k){
if(l >= L && r <= R) return segment[k];
else{
int m = l + ((r - l) >> 1);
int sum = 0;
if(L <= m) sum += sumRange(L, R, l, m, k << 1);
if(R > m) sum += sumRange(L, R, m + 1, r, k << 1 | 1);
return sum;
}
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* obj.update(i,val);
* int param_2 = obj.sumRange(i,j);
*/class NumArray {
private:
vector<int> sum_;
vector<int> nums_;
public:
NumArray(vector<int>& nums): nums_(std::move(nums)) {
int size = nums_.size();
if(size == 0) return;
sum_.resize(size, 0);
sum_[0] = nums_[0];
for(int i = 1; i < size; i++){
sum_[i] = sum_[i - 1] + nums_[i];
}
}
void update(int i, int val) {
int pre = nums_[i];
nums_[i] = val;
int diff = val - pre;
for(int j = i; j < sum_.size(); j++){
sum_[j] += diff;
}
}
int sumRange(int i, int j) {
return sum_[j] - sum_[i] + nums_[i];
}
};
/**
* Your NumArray object will be instantiated and called as such:
* NumArray* obj = new NumArray(nums);
* obj->update(i,val);
* int param_2 = obj->sumRange(i,j);
*/