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]);
}
};
上一篇: jquery插件开发
下一篇: MFC编辑框CEdit中的气泡提示方法
推荐阅读
-
Leetcode 307. 区域和检索 - 数组可修改
-
Leetcode 307. 区域和检索 - 数组可修改
-
LeetCode-307. 区域和检索 - 数组可修改
-
LeetCode 307. 区域和检索 - 数组可修改
-
Leetcode-307. 区域和检索 - 数组可修改 Range Sum Query - Mutable (线段树Segment Tree)-超详细Python
-
Leetcode-303.区域和检索-数组不可变
-
【Leetcode每日笔记】303. 区域和检索 - 数组不可变(Python)
-
Leetcode-303.区域和检索-数组不可变
-
【Leetcode每日笔记】303. 区域和检索 - 数组不可变(Python)
-
Leetcode 区域和检索 - 数组可修改