2020-04-03 12:35:23
问题描述：
已知一个数列，你需要进行下面两种操作：
1.将一个区间每一个数加上x
2.求出某一个数的值
输入：
原数组为A。为了方便，A[0]为0.实际数列从A[1]开始。
操作通过4元组给出。
对于每个4元组（a,b,c,d）：
如果a=0 要求A[b]-A[c]区间的值都增加d(修改)。
如果a=1 要求得到A[b]的值。其中c,d不起作用(查询)。
输出：
为了减少输出数据量。将操作2(询问)的所有值异或(^) 后返回。
样例
样例 1:
输入：[0,1,2,3,4],[[1,1,0,0],[0,1,2,1],[1,2,0,0]] 输出：2 解释： 第一个操作返回A [1] = 1 第二个操作改变A为 [0,2,3,3,4] 第三个操作返回A [1] = 3 所以 1 ^ 3 = 2
样例 2:
输入：[0,1],[[1,1,0,0]] 输出：1 解释：第一个操作返回A [1] = 1,答案为 1。
注意事项
问题求解：
int[] bit;
public long intervalsAddAndGetValue(int[] A, int[][] operations) {
int n = A.length;
bit = new int[n];
for (int i = 1; i < n; i++) {
update(i, A[i]);
update(i + 1, -A[i]);
}
long res = 0;
for (int[] op : operations) {
if (op[0] == 0) {
update(op[1], op[3]);
update(op[2] + 1, -op[3]);
}
else {
res ^= query(op[1]);
}
}
return res;
}
private void update(int idx, int delta) {
for (int i = idx; i < bit.length; i += (i & -i)) {
bit[i] += delta;
}
}
private int query(int idx) {
int res = 0;
for (int i = idx; i > 0; i -= (i & -i)) {
res += bit[i];
}
return res;
}
数据结构-树状数组-区间修改单点求值-1750. 区间加和求值
原文：https://www.cnblogs.com/hyserendipity/p/12625785.html