如何解决线段树上的问题
How can I solve the problem on the segment tree
我有一个数组 a[0..n - 1]。我有两种类型的操作：
- 总和 l r:
总和 = a[l] * 1 + a[l+1] * 2 + ... + a[r] * (r - l)
- 更新索引值：a[index] = value
我如何为这个任务修改标准和线段树？
为数组 b 的总和存储第二个线段树，其中 b[i] = (i+1) * a[i]。然后，设置 a[index] = value 也应该用 b[index] = value * (index + 1).
更新第二个线段树
计算你想要的和，给定查询a和b的正常子数组和的能力：
special_sum(l, r) = a[l] * 1 + a[l+1] * 2 + ... + a[r] * (r - l)
can be rewritten as:
(l+1) * a[l] + (l+2) * a[l+1] + ... + (r) * a[r]
- l * (a[l] + a[l+1] + ... + a[r])
which becomes
b[l] + b[l+1] + ... + b[r]
- l * (a[l] + a[l+1] + ... + a[r])
我有一个数组 a[0..n - 1]。我有两种类型的操作：
- 总和 l r: 总和 = a[l] * 1 + a[l+1] * 2 + ... + a[r] * (r - l)
- 更新索引值：a[index] = value
我如何为这个任务修改标准和线段树？
为数组 b 的总和存储第二个线段树，其中 b[i] = (i+1) * a[i]。然后，设置 a[index] = value 也应该用 b[index] = value * (index + 1).
计算你想要的和，给定查询a和b的正常子数组和的能力：
special_sum(l, r) = a[l] * 1 + a[l+1] * 2 + ... + a[r] * (r - l)
can be rewritten as:
(l+1) * a[l] + (l+2) * a[l+1] + ... + (r) * a[r]
- l * (a[l] + a[l+1] + ... + a[r])
which becomes
b[l] + b[l+1] + ... + b[r]
- l * (a[l] + a[l+1] + ... + a[r])