题目大意：给你一个数组，让你求一个范围之内所有元素的和，数组元素可以更改。
Problem:
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:
|
1 2 3 4 5 |
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.
Idea:
Fenwick Tree
Solution:
C++
Time complexity:
init O(nlogn)
query: O(logn)
update: O(logn)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
// Author: Huahua // Running time: 83 ms class FenwickTree { public: FenwickTree(int n): sums_(n + 1, 0) {} void update(int i, int delta) { while (i < sums_.size()) { sums_[i] += delta; i += lowbit(i); } } int query(int i) const { int sum = 0; while (i > 0) { sum += sums_[i]; i -= lowbit(i); } return sum; } private: static inline int lowbit(int x) { return x & (-x); } vector<int> sums_; }; class NumArray { public: NumArray(vector<int> nums): nums_(std::move(nums)), tree_(nums_.size()) { for (int i = 0; i < nums_.size(); ++i) tree_.update(i + 1, nums_[i]); } void update(int i, int val) { tree_.update(i + 1, val - nums_[i]); nums_[i] = val; } int sumRange(int i, int j) { return tree_.query(j + 1) - tree_.query(i); } private: vector<int> nums_; FenwickTree tree_; }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
// Author: Huahua // Running time: 130 ms class NumArray { FenwickTree tree_; int[] nums_; public NumArray(int[] nums) { nums_ = nums; tree_ = new FenwickTree(nums.length); for (int i = 0; i < nums.length; ++i) tree_.update(i + 1, nums[i]); } public void update(int i, int val) { tree_.update(i + 1, val - nums_[i]); nums_[i] = val; } public int sumRange(int i, int j) { return tree_.query(j + 1) - tree_.query(i); } class FenwickTree { int sums_[]; public FenwickTree(int n) { sums_ = new int[n + 1]; } public void update(int i, int delta) { while (i < sums_.length) { sums_[i] += delta; i += i & -i; } } public int query(int i) { int sum = 0; while (i > 0) { sum += sums_[i]; i -= i & -i; } return sum; } } } |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
""" Author: Huahua Running time: 192 ms (< 90.00%) """ class FenwickTree: def __init__(self, n): self._sums = [0 for _ in range(n + 1)] def update(self, i, delta): while i < len(self._sums): self._sums[i] += delta i += i & -i def query(self, i): s = 0 while i > 0: s += self._sums[i] i -= i & -i return s class NumArray: def __init__(self, nums): self._nums = nums self._tree = FenwickTree(len(nums)) for i in range(len(nums)): self._tree.update(i + 1, nums[i]) def update(self, i, val): self._tree.update(i + 1, val - self._nums[i]) self._nums[i] = val def sumRange(self, i, j): return self._tree.query(j + 1) - self._tree.query(i) |
Solution 2: Segment Tree
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
// Author: Huahua, running time: 24 ms class SegmentTreeNode { public: SegmentTreeNode(int start, int end, int sum, SegmentTreeNode* left = nullptr, SegmentTreeNode* right = nullptr): start(start), end(end), sum(sum), left(left), right(right){} SegmentTreeNode(const SegmentTreeNode&) = delete; SegmentTreeNode& operator=(const SegmentTreeNode&) = delete; ~SegmentTreeNode() { delete left; delete right; left = right = nullptr; } int start; int end; int sum; SegmentTreeNode* left; SegmentTreeNode* right; }; class NumArray { public: NumArray(vector<int> nums) { nums_.swap(nums); if (!nums_.empty()) root_.reset(buildTree(0, nums_.size() - 1)); } void update(int i, int val) { updateTree(root_.get(), i, val); } int sumRange(int i, int j) { return sumRange(root_.get(), i, j); } private: vector<int> nums_; std::unique_ptr<SegmentTreeNode> root_; SegmentTreeNode* buildTree(int start, int end) { if (start == end) { return new SegmentTreeNode(start, end, nums_[start]); } int mid = start + (end - start) / 2; auto left = buildTree(start, mid); auto right = buildTree(mid + 1, end); auto node = new SegmentTreeNode(start, end, left->sum + right->sum, left, right); return node; } void updateTree(SegmentTreeNode* root, int i, int val) { if (root->start == i && root->end == i) { root->sum = val; return; } int mid = root->start + (root->end - root->start) / 2; if (i <= mid) { updateTree(root->left, i, val); } else { updateTree(root->right, i, val); } root->sum = root->left->sum + root->right->sum; } int sumRange(SegmentTreeNode* root, int i, int j) { if (i == root->start && j == root->end) { return root->sum; } int mid = root->start + (root->end - root->start) / 2; if (j <= mid) { return sumRange(root->left, i, j); } else if (i > mid) { return sumRange(root->right, i, j); } else { return sumRange(root->left, i, mid) + sumRange(root->right, mid + 1, j); } } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
[…] 花花酱 307. Range Sum Query – Mutable […]