前言
又是好久没有更新了
正文
问题来源
本问题来自leetcode上的307题。
问题描述
给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。
update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。
示例 1:
Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
分析：
看网上解答写的
Fenwick树或者树状数组或二元索引树（英语：Binary Indexed Tree）
type NumArray struct {
BitArr []int
Nums []int
}
func Constructor(nums []int) NumArray {
bitArr := make([]int, len(nums)+1)
for i := 0; i < len(nums); i++ {
bitArr[i+1] = nums[i]
}
for i := 1; i < len(bitArr); i++ {
j := i + i & (-i)
if j < len(bitArr) {
bitArr[j] += bitArr[i]
}
}
return NumArray{bitArr, nums}
}
func (this *NumArray) Update(i int, val int) {
delta := val - this.Nums[i]
this.Nums[i] = val
i = i + 1
for i < len(this.BitArr) {
this.BitArr[i] += delta
i = i + i & (-i)
}
}
func (this *NumArray) prefix(i int) int {
i++
sum := 0
for i > 0 {
sum += this.BitArr[i]
i -= i & (-i)
}
//fmt.Println(sum)
return sum
}
func (this *NumArray) SumRange(i int, j int) int {
return this.prefix(j) - this.prefix(i-1)
}
官方线段树解法
int[] tree;
int n;
public NumArray(int[] nums) {
if (nums.length > 0) {
n = nums.length;
tree = new int[n * 2];
buildTree(nums);
}
}
private void buildTree(int[] nums) {
for (int i = n, j = 0; i < 2 * n; i++, j++)
tree[i] = nums[j];
for (int i = n - 1; i > 0; --i)
tree[i] = tree[i * 2] + tree[i * 2 + 1];
}
void update(int pos, int val) {
pos += n;
tree[pos] = val;
while (pos > 0) {
int left = pos;
int right = pos;
if (pos % 2 == 0) {
right = pos + 1;
} else {
left = pos - 1;
}
// parent is updated after child is updated
tree[pos / 2] = tree[left] + tree[right];
pos /= 2;
}
}
public int sumRange(int l, int r) {
// get leaf with value 'l'
l += n;
// get leaf with value 'r'
r += n;
int sum = 0;
while (l <= r) {
if ((l % 2) == 1) {
sum += tree[l];
l++;
}
if ((r % 2) == 0) {
sum += tree[r];
r--;
}
l /= 2;
r /= 2;
}
return sum;
}
总结：
勤思考。
结语
不管怎么样好好加油。
