欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-05 15:39:55
...

给定一个整数数组 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 说明:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/range-sum-query-mutable
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

两种方法:数组和线段树

56ms

//307-2___线段树
class NumArray {
public:
	vector<int> data;
	vector<int> tree;
	NumArray(vector<int>& nums) {
        if (nums.size() == 0) {
			return;
		}
		tree=vector<int>(4*nums.size(),0);
		data.assign(nums.begin(), nums.end());
		BuildSegmentTree(0, 0, data.size() - 1);
	}
	void BuildSegmentTree(int TreeIndex, int left, int right) {
		if (left == right) {
			tree[TreeIndex] = data[left];
			return;
		}
		int LeftTreeIndex = 2 * TreeIndex + 1;
		int RightTreeIndex = 2 * TreeIndex + 2;
		int mid = left + (right - left) / 2;
		BuildSegmentTree(LeftTreeIndex, left, mid);
		BuildSegmentTree(RightTreeIndex, mid + 1, right);
		tree[TreeIndex] = tree[LeftTreeIndex] + tree[RightTreeIndex];
	}

	void update(int i, int val) {
		if (i<0 || i>data.size() - 1) {
			return;
		}
		data[i] = val;
		set(0, 0, data.size() - 1, i, val);
	}
	void set(int TreeIndex, int l, int r, int index, int e) {
		if (l == r) {
			tree[TreeIndex] = e;
			return;
		}
		int LeftTreeIndex = 2 * TreeIndex + 1;
		int RightTreeIndex = 2 * TreeIndex + 2;
		int mid = l + (r - l) / 2;
		if (index >= mid + 1) {
			set(RightTreeIndex, mid + 1, r, index, e);
		}
		else {
			set(LeftTreeIndex, l, mid, index, e);
		}
		tree[TreeIndex] = tree[LeftTreeIndex] + tree[RightTreeIndex];
	}

	int sumRange(int i, int j) {
		if (i > j || i<0 || j>data.size() - 1) {
			return -1;
		}
		return query(0, 0, data.size() - 1, i, j);
	}
	int query(int TreeIndex, int left, int right, int queryL, int queryR) {
		if (left == queryL&&right == queryR) {
			return tree[TreeIndex];
		}
		int LeftTreeIndex = 2 * TreeIndex + 1;
		int RightTreeIndex = 2 * TreeIndex + 2;
		int mid = left + (right - left) / 2;
		if (queryL >= mid + 1) {
			return query(RightTreeIndex, mid + 1, right, queryL, queryR);
		}
		else if (queryR <= mid) {
			return query(LeftTreeIndex, left, mid, queryL, queryR);
		}
		int lrec = query(LeftTreeIndex, left, mid, queryL, mid);
		int rrec = query(RightTreeIndex, mid + 1, right, mid + 1, queryR);
		return lrec + rrec;
	}

};

244ms

//307-1___差方法
class NumArray1 {
public:
	vector<int> sum1;
	vector<int> nums1;
	NumArray1(vector<int>& nums) {
		int sum = 0;
		sum1.push_back(sum);
		for (int i = 0; i < nums.size(); i++) {
			sum = sum + nums[i];
			sum1.push_back(sum);
		}
		nums1.assign(nums.begin(), nums.end());
	}

	void update(int i, int val) {
		int temp = val - nums1[i];
		nums1[i] = val;
		for (int j = i + 1; j < sum1.size(); j++) {
			sum1[j] = sum1[j] + temp;
		}
	}

	int sumRange(int i, int j) {
		return (sum1[j + 1] - sum1[i]);
	}
};