1.update:3/30
参考:https://www.cnblogs.com/guanlexiangfan/p/15320387.html
线段树区间修改问题:
有关lazy tag的解释:1.当这段区间被第n次询问修改的时候,如果之前的n-1次询问也有修改过这段区间 才会使用懒标记来等效之前n-1次修改的效果
2.因为线段树并不修改数组本身 因此多次动态修改区间 需要动态的lazy tag 来记录每次改变区间的位置。
![segtree.jpg](https://cdn.acwing.com/media/article/image/2024/03/30/375342_a3b77476ee-segtree.jpg)
3. 相当于每次不用到的区间 暂时挂机 只有下次可能用到这些区间时
才将懒标记里的数据连带给sum 例如图中我修改[2,4]这个区间, 那么
这些区间的子区间是无需遍历的 就给他们的父节点打上懒标记
等到修改他们的时候,父节点会下传给他们.
相当于某种记账本:当再次记这类帐时候肯定不会从头一笔一笔记
而是在之前这类帐的收支余额上记。
因为线段树解决的一般是
带有多次询问的动态问题,因此回溯的push_down函数
是用来为多次查询带来便利
第一次区间修改肯定不会用到push_down的懒标记累加
因为一旦遇到覆盖区间会直接return;
//线段树 区间修改lazytag 模板O(logn).
//其中的区间修改和区间询问 都可以做 单点修改和单点询问
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int n;//区间长度
int a[N];
struct seg_tree
{
int l, r;
int sum;
int tag;
}seg[4 * N];//开4倍区间长度
void push_up(int no)//将子树的值加回父节点
{
seg[no].sum = seg[no << 1].sum + seg[no << 1 | 1].sum;
}
void push_down(int u)//lazytag下传模板
{
auto &root = seg[u], &lc = seg[u << 1], &rc = seg[u << 1 | 1];//带取地址符 对原数组修改
if(seg[u].tag)//向子树传懒标记 将之前的懒标记给加上 并且将之前的修改的值也加上
lc.tag += root.tag, lc.sum += root.tag * (lc.r - lc.l + 1);
rc.tag += root.tag, rc.sum += root.tag * (rc.r - rc.l + 1);//注意这里加的应该是root的
懒标记的数量。
root.tag = 0;
}
void init(int u, int l, int r)//建线段树 模板
{
if(l == r)
{
seg[u] = {l, r, a[l]};//此时为长度为一的点 初始化
return;
}
seg[u] = {l, r};
int mid = l + r >> 1;
init(u << 1, l, mid);
init(u << 1 | 1, mid + 1, r);
push_up(u);
}
void modify(int u, int l, int r, int d)//区间修改模板
{
if(seg[u].l >= l && seg[u].r <= r)//区间被覆盖 因此先加上这次要加上的数字
{
seg[u].sum += (seg[u].r - seg[u].l + 1) * d;
seg[u].tag += d;//在完成此次加法后,加入lazy tag,在之后修改相同的区间时直接减去即可
return;
}
push_down(u);//从祖宗节点向下遍历一层 看是否有懒标记
int mid = seg[u].l + seg[u].r >> 1;
if(l <= mid)modify(u << 1, l, r, d);
if(mid + 1 <= r)modify(u << 1 | 1, l, r, d);
push_up(u);
}
int main()
{
cin >> n;
for(int i = 1;i <= n;i++)cin >> a[i];
int l, r, d;
cin >> l >> r >> d;
init(1, 1, n);//初始化线段树
cout << seg[1].sum << " " << seg[2].sum << " " << seg[3].sum;
cout << endl;
modify(1, l, r, d);
cout << seg[1].sum << " " << seg[2].sum << " " << seg[3].sum;
return 0;
}
LL query (int u,int l,int r) {//区间询问模板
if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
push_down (u);//询问只需要推懒标记而不需要push_up sum因为并没有值修改
int mid = tr[u].l + tr[u].r >> 1;
LL ans = 0;
if (l <= mid) ans += query (u << 1,l,r);
if (r >= mid + 1) ans += query (u << 1 | 1,l,r);
return ans;
}
//区间查询最大值 模板 maxnum 等同于上文的sum
int query(int u,int l,int r)//强调:这里指的是查询u结点中与[l,r]交集部分的最大值
{
if(tr[u].l>=l&&tr[u].r<=r)//完全包含,则结束
return tr[u].maxnum;
int mid=tr[u].l+tr[u].r>>1;
int maxnum=1-pow(2,32);//-0x3f3f3f3f在这题的2^32-1要求中还不够大,故这样写了
if(l<=mid)//左边区间还有元素没查到
maxnum=max(maxnum,query(u<<1,l,r));
if(r>mid)//右边区间还有元素没查到
maxnum=max(maxnum,query(u<<1|1,l,r));
return maxnum;
}