单点修改，区间查询
const int maxn = 500005 * 4; //线段树范围要开4倍 struct Tree { int l, r, sum, maxx; }; Tree node[maxn]; //node[maxn]为线段树处理数组 int a[maxn]; //a[maxn]为原数组 void PushUp(int i) { node[i].sum = node[i << 1].sum + node[(i << 1) | 1].sum; //线段树求和 node[i].maxx = max(node[i << 1].maxx, node[(i << 1) | 1].maxx); // 线段树求最大值 } //创建一个tree void build(int i, int l, int r) { node[i].l = l; node[i].r = r; if (l == r) { node[i].maxx = a[l]; node[i].sum = a[l]; return; } int mid = (l + r) >> 1; build(i << 1, l, mid);// 建立mid左边的树 i<<1所表示的是 tree 上的所在点 build((i << 1) | 1, mid + 1, r); //建立mid右边的树采用递推 PushUp(i); } int getsum(int i, int l, int r) { if (node[i].l == l&&node[i].r == r) return node[i].sum; int mid = (node[i].l + node[i].r) >> 1; if (r <= mid) { return getsum(i << 1, l, r); } else if (l > mid) { return getsum((i << 1) | 1, l, r); } else { return getsum(i << 1, l, mid) + getsum((i << 1) | 1, mid + 1, r); } } int getmax(int i, int l, int r) { if (node[i].l == l&&node[i].r == r) return node[i].maxx; int mid = (node[i].l + node[i].r) >> 1; if (r <= mid) { return getmax(i << 1, l, r); } else if (l>mid) { return getmax((i << 1) | 1, l, r); } else { return max(getmax(i << 1, l, mid), getmax((i << 1) | 1, mid + 1, r)); } } void add(int i, int k, int v) //当前更新的节点的编号为i（一般是1为初始编号，具体得看建立树时使用的第一个编号是什么）。 { //k为需要更新的点的位置，v为修改的值的大小 if (node[i].l == k&&node[i].r == k) //左右端点均和k相等，说明找到了k所在的叶子节点 { node[i].sum += v; node[i].maxx += v; return; //找到了叶子节点就不需要在向下寻找了 } int mid = (node[i].l + node[i].r) / 2; if (k <= mid) a { add(i << 1, k, v); } else { add((i << 1) | 1, k, v); } PushUp(i); }
区间修改，区间查询
const int N = 100005; LL a[N]; //a[N]储存原数组 LL lazy[N << 2]; //lazy用来记录该节点的每个数值应该加多少 int n, q; struct Tree { int l, r; LL sum; int mid() { return (l + r) >> 1; } }tree[N<<2]; void PushUp(int rt) { tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum; } void PushDown(int rt,int m) { if (lazy[rt]) { lazy[rt << 1] += lazy[rt]; lazy[rt << 1 | 1] += lazy[rt]; tree[rt << 1].sum += lazy[rt] * (m - (m >> 1)); tree[rt << 1 | 1].sum += lazy[rt] * (m >> 1); lazy[rt] = 0; } } void build(int l, int r, int rt) { tree[rt].l = l; tree[rt].r = r; lazy[rt] = 0; if (l == r) { tree[rt].sum = a[l]; return; } int m = tree[rt].mid(); build(l, m, (rt << 1)); build(m + 1, r, (rt << 1 | 1)); PushUp(rt); } void update(LL c, int l, int r, int rt) { if (tree[rt].l == l&&tree[rt].r==r) { lazy[rt] += c; tree[rt].sum += c*(r - l + 1); return; } if (tree[rt].l == tree[rt].r)return; int m = tree[rt].mid(); PushDown(rt, tree[rt].r - tree[rt].l + 1); if (r <= m)update(c, l, r, rt << 1); else if (l > m)update(c, l, r, rt << 1 | 1); else { update(c, l, m, rt << 1); update(c, m + 1, r, rt << 1 | 1); } PushUp(rt); } LL Query(int l, int r, int rt) { if (l == tree[rt].l&&r == tree[rt].r) { return tree[rt].sum; } int m = tree[rt].mid(); PushDown(rt, tree[rt].r - tree[rt].l + 1); LL res = 0; if (r <= m)res += Query(l, r, rt << 1); else if (l > m)res += Query(l, r, rt << 1 | 1); else { res += Query(l, m, rt << 1); res += Query(m + 1, r, rt << 1 | 1); } return res; }