最朴素的线段树

#include<cstring> #include<cstdio> #include<algorithm> #include<iostream> using namespace std; const int N = 2e5 + 10; using ll = long long; int n; struct node { int l, r; ll sum, lz; }tree[N << 2]; inline int ls(int cur) { //求左子节点 return cur << 1; } inline int rs(int cur) { //求右子节点 return (cur << 1) | 1; } void push_up(int cur) { //左右子树更新当前区间的值 tree[cur].sum = tree[ls(cur)].sum + tree[rs(cur)].sum; } void push_down(int cur) { //在查询时，如果子树的值还未进行更新，则对子树进行更新 if (tree[cur].lz) { tree[ls(cur)].sum += (tree[ls(cur)].r - tree[ls(cur)].l + 1) * tree[cur].lz; tree[ls(cur)].sum += (tree[rs(cur)].r - tree[rs(cur)].l + 1) * tree[cur].lz; tree[ls(cur)].lz += tree[cur].lz; tree[rs(cur)].lz += tree[cur].lz; tree[cur].lz = 0; } } void build(int cur, int l, int r) { tree[cur].l = l; tree[cur].r = r; if (l == r) { //已经到了叶子节点 ll a; cin >> a; tree[cur].sum = a; return; } int mid = (tree[cur].l + tree[cur].r) >> 1; build(ls(cur), l, mid); build(rs(cur), mid + 1, r); push_up(cur); } void update(int cur, int l, int r, int v) { if (tree[cur].l == l and tree[cur].r == r) { //当前节点正好是要修改的区间 tree[cur].sum += (r - l + 1) * v; tree[cur].lz += v; return; } //遍历到当前节点时，顺便将子节点的值给更新 push_down(cur); int mid = (tree[cur].l + tree[cur].r) >> 1; if (r <= mid) { //要更新的区间都在当前节点区间的左边 update(ls(cur), l, r, v); } else if (l > mid) { update(rs(cur), l, r, v); } else { update(ls(cur), l, mid, v); update(rs(cur), mid + 1, r, v); } //更新完子节点之后将自己也进行更新 push_up(cur); } int query(int cur, int l, int r) { if (tree[cur].l == l and tree[cur].r == r) { return tree[cur].sum; } //对子节点进行查询时,先将子节点值进行更新 push_down(cur); int mid = (tree[cur].l + tree[cur].r) >> 1; if (r <= mid) { return query(ls(cur), l, r); } else if (l > mid) { return query(rs(cur), l, r); } else { return query(ls(cur), l, mid) + query(rs(cur), mid + 1, r); } } int main() { #ifndef ONLINE_JUDGE freopen("D:/VS CODE/C++/in.txt", "r", stdin); freopen("D:/VS CODE/C++/out.txt", "w", stdout); #endif cin >> n; build(1, 1, n); return 0; }