树状数组是个好东西,写起来也相对好看。但是操作比较局限,区间修改就掉回\(O(nlogn)\), 那还不如 \(O(n)\)。线段树完美的解决问题。
线段树,也可以理解的一堆线段组成的树。
大致如上,有一线段 \([l, r]\) 当 \(l \ne r\) 可化为 \([l, mid]\) , \([mid + 1, r]\)
PS: \(mid = (l + r) / 2\)
增加
此操作 不是 新加节点,是将一段区间增加一个数。
将 [2, 9] 每个数增加 1
像这样通过递归的方式修改这些节点,然后我们惊喜的发现,访问了 \(n logn\) 个节点......似乎不如没有
这个时候lazy_tag登场(懒人tag)
蓝色的就是lazy_tag(下文称为tag),标记增加了多少, 这时 \([2,2], [3,3],[4,5], [6,8], [9,9]\) 都有 tag = 1。
用处放到下文
查询
这里,我们可以查询区间的和
在上例子里我们查询 [1, 1]时,不会有问题,查询 [1, 2]时,不会有问题, 查询 [1, 10]时,不会有问题, 但是查询 [6, ]7时,会有问题, 因为没有修改到。
因为 [6, 8] 被标有tag, 然而,在访问 [6, 7]时一定会访问到6, 8,那么我们便可以将tag传下来。
也就是不访问就不修改。
运用以上方案,就可以实现单点修改,单点查询,区间修改(同增同减), 区间查询。
#include<iostream>
using namespace std;
const long long kMaxN = 1e5 + 5;
long long n, m, a[kMaxN << 2]; //注意开大4倍
struct L {
long long sum, tag;
} sgt[kMaxN << 2];
void push_up(long long rt) { //更新这个节点
sgt[rt].sum = sgt[rt << 1].sum + sgt[rt << 1 | 1].sum;
}
void build_tree(long long rt, long long l, long long r) { //建树
sgt[rt].tag=0;
if (l == r) {
sgt[rt].sum = a[l];
return;
}
long long mid = l + r >> 1;
build_tree(rt << 1, l, mid), build_tree(rt << 1 | 1, mid + 1, r);
push_up(rt);
}
void add_tag(long long rt, long long l, long long r,long long d) {//建立tag
sgt[rt].tag += d;
sgt[rt].sum += d * (r - l + 1);//值也增加
}
void push_down(long long rt, long long l, long long r) { //tag往下传
if (sgt[rt].tag) {
long long mid = l + r >> 1;
add_tag(rt << 1, l, mid, sgt[rt].tag);
add_tag(rt << 1 | 1, mid + 1, r, sgt[rt].tag);
sgt[rt].tag = 0;
}
}
void update(long long L, long long R, long long rt, long long l, long long r, long long d){ //更新[l, r]的值 + d
if (L <= l && r <= R) {
add_tag(rt, l, r, d);
return;
}
push_down(rt, l, r);
long long mid = l + r >> 1;
if (L <= mid) {
update(L, R, rt << 1, l, mid, d);
} if (mid < R) {
update(L, R, rt << 1 | 1, mid + 1, r, d);
}
push_up(rt);
}
long long query(long long L, long long R, long long rt, long long l, long long r) {//找到 [L, R] 的和
if (L <= l && r <= R) {
return sgt[rt].sum;
}
push_down(rt, l, r);
long long mid = l + r >> 1, ans = 0;
if (L <= mid) {
ans += query(L, R, rt << 1, l, mid);
}
if (mid < R) {
ans += query(L, R, rt << 1 | 1, mid + 1, r);
}
return ans;
}
int main(){
cin >> n >> m;
for (long long i = 1; i <= n; i++) {
cin >> a[i];
}
build_tree(1, 1, n);
for(long long i = 1, a, x, y, d; i <= m; i++) {
cin >> a >> x >> y;
if (a == 1) {
cin >> d;
update(x, y, 1, 1, n, d);
} else {
cout << query(x, y, 1, 1, n) << '\n';
}
}
return 0;
}
标签:线段,mid,long,查询,修改,tag
From: https://www.cnblogs.com/jiangyuchen12/p/17685901.html