普通线段树（单点查询）

#includebits/stdc.h#define int long longusing namespace std;const int N1e6 5;int n,m;int a[N];int node[N 2];// 四倍空间// 线段树建树// root 当前区间节点的编号// [l, r] 表示当前节点的区间范围void build(int root, int l, int r){// 退出条件if(l r){node[root] a[l];// 到末端叶子节点了,这个区间表示的范围是【l,l】;return ;}int mid (l r) / 2;// 二叉树对半分找到区间中间点build(root * 2, l, mid);// 先建左儿子 范围是【l,mid】build(root * 2 1, mid 1, r);// 右儿子 范围是【mid1r】// 父亲 左儿子 右儿子node[root] node[root * 2] node[root * 2 1];// 从下到上建树}// 普通线段树区间查询// root 当前区间节点的编号// [l, r] 表示当前节点的区间范围// [L, R] 表示的是我要查询的区间范围 L、R值不变int query(int root, int l, int r, int L, int R) {if (L l r R) { // 发现【lr】已经包含在【LR】中那么直接可以返回答案return node[root];// 当前节点的值是答案的一部分直接用不用推了}int mid (l r) / 2;// 计算中心// 更新儿子之前记得下推懒标记int sum 0;// 区间和if (L mid) sum query(root * 2, l, mid, L, R); // 说明有一部分答案在左边if (R mid) sum query(root * 2 1, mid 1, r, L, R); // 说明有一部分答案在右边return sum;}// 单点修改 把下标为idx的改为val// root 当前区间节点的编号// [l, r] 表示当前节点的区间范围// idx 表示要修改的区间下标val 表示要修改的值void update(int root, int l, int r, int idx, int val) {if(l r){node[root] val;return ;}int mid (l r) / 2; // 找左右儿子中心点// 更新儿子之前记得下推懒标记// 要更新的区间左端点 中心点说明左儿子至少有一部分需要更新if (idx mid) update(root * 2, l, mid, idx, val);// mid是左儿子的最后一个位置// 要更新的区间右端点 中心点说明右儿子至少有一部分需要更新if (idx mid) update(root * 2 1, mid 1, r, idx, val);// 更新父亲node[root] node[root * 2] node[root * 2 1];}signed main(){cin n m;for(int i 1;i n;i){cin a[i];}build(1, 1, n);// 建树while(m–){int type;cin type;if(type 1){int x, k;cin x k;update(1, 1, n, x, k);}else{int x, y;cin x y;cout query(1, 1, n, x, y) endl;// 查询}}return 0;}