|
|
//博文：https://codeforces.com/blog/entry/18051
|
|
|
// zkw 单点修改 区间查询 例子
|
|
|
#include <iostream>
|
|
|
#include <cstring>
|
|
|
#include <algorithm>
|
|
|
|
|
|
using namespace std;
|
|
|
//快读
|
|
|
int read() {
|
|
|
int x = 0, f = 1;
|
|
|
char ch = getchar();
|
|
|
while (ch < '0' || ch > '9') {
|
|
|
if (ch == '-') f = -1;
|
|
|
ch = getchar();
|
|
|
}
|
|
|
while (ch >= '0' && ch <= '9') {
|
|
|
x = (x << 3) + (x << 1) + (ch ^ 48);
|
|
|
ch = getchar();
|
|
|
}
|
|
|
return x * f;
|
|
|
}
|
|
|
|
|
|
const int N = 1e5 + 10; // limit for array size
|
|
|
int n; // array size
|
|
|
int t[N << 1]; // 2倍内存
|
|
|
|
|
|
void build() { //构建zkw线段树
|
|
|
for (int i = 0; i < n; i++) t[n + i] = read(); //数据从下标n开始读
|
|
|
for (int i = n - 1; i; i--) t[i] = t[i << 1] + t[i << 1 | 1]; //父亲结点们更新统计信息sum和
|
|
|
}
|
|
|
|
|
|
//单点修改
|
|
|
void modify(int p, int value) { // set value at position p
|
|
|
//① 将指定位置p的对应叶子结点位置修改为value
|
|
|
//② 修改指定结点的父亲们,p>>1就是不断的向上找父亲节点,不断向上更新sum和
|
|
|
for (t[p += n] = value; p > 1; p >>= 1) t[p >> 1] = t[p] + t[p ^ 1];
|
|
|
}
|
|
|
|
|
|
//区间查询
|
|
|
int query(int l, int r) { // sum on interval [l, r)
|
|
|
int res = 0;
|
|
|
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
|
|
|
//① 如果l是奇数，l是父亲的右孩子(看一下上面的图，确实是右孩子)
|
|
|
// (1) 此时，只有它自己有用,它的父亲不包含在查询区间内。自己加上，把略过即可
|
|
|
// (2) 怎么略过呢？巧妙的办法：本轮次不加自己父亲，下软移动到右边的兄弟节点的父亲上去! l= (l+1) >> 1
|
|
|
//② 如果l是偶数，那么l就是父亲的左儿子，整个区间完整命中，直接研究它父亲的sum即可， l>>=1
|
|
|
if (l & 1) res += t[l++];
|
|
|
|
|
|
//与上面代码对称的写法
|
|
|
if (r & 1) res += t[--r];
|
|
|
}
|
|
|
return res;
|
|
|
}
|
|
|
|
|
|
/*
|
|
|
输入样例：
|
|
|
15
|
|
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
|
|
|
|
|
|
输出样例：
|
|
|
52
|
|
|
|
|
|
手工验证
|
|
|
[3,11)
|
|
|
3+4+5+6+7+8+9+10=52 正确
|
|
|
*/
|
|
|
int main() {
|
|
|
//文件输入输出
|
|
|
#ifndef ONLINE_JUDGE
|
|
|
freopen("zkw_Study_1.in", "r", stdin);
|
|
|
#endif
|
|
|
n = read();
|
|
|
|
|
|
build();
|
|
|
|
|
|
//单点修改的例子,后面查询没用上这个修改
|
|
|
modify(0, 1);
|
|
|
|
|
|
//区间查询,左闭右开
|
|
|
printf("%d\n", query(3, 11));
|
|
|
return 0;
|
|
|
} |
