LeetCode-307. 区域和检索 - 数组可修改

307. 区域和检索 - 数组可修改

难度中等80收藏分享切换为英文关注

通过次数

4,680

提交次数

9,083

题目描述

评论 (56)

题解(20)New

提交记录

给定一个整数数组  nums，求出数组从索引 i 到 j  (i ≤ j) 范围内元素的总和，包含 i,  j 两点。

update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。

示例:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

说明:

1. 数组仅可以在 update 函数下进行修改。
2. 你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。

 

 没用线段树，没用树状数组。写的特简单，虽然时间长也过了，先贴一个。

 线段树正在学习当中。

#include<iostream>
#include<stdlib.h>
#include<vector>

using namespace std;

/**
* 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 {
public:
	NumArray(vector<int>& nums) {
		this->numArray = nums;
	}

	void update(int i, int val) {
		this->numArray[i] = val;
	}

	int sumRange(int i, int j) {
		ArraySum = 0;
		for (int start = i; start <= j; start++) {
			ArraySum += this->numArray[start];
		}
		return  ArraySum;
	}

private:
	vector<int> numArray;
	int ArraySum;
};

int mainx() {
	vector<int> nums = { 1,3,5 };
	NumArray *ps = new NumArray(nums);
	cout << ps->sumRange(0, 2) << endl;
	ps->update(1, 2);
	cout << ps->sumRange(0, 2) << endl;


	system("pause");
	return 0;
}