线段树基本知识
线段树=分治法+二叉树结构+Lazy—Tag技术。
线段树样式[1,10]:
线段树常用操作:
1.pushup(从下往上)
1.1(hard) pushdown(懒标记,后面写)
2.build(建立)
3.modify(修改)
4.query(查询)
先来看:
线段树的build
前提结论:当做二叉树看:对于编号为x的点:
父节点:向下取整(x/2),左儿子:2x,右儿子:2x+1
//u表示当前线段树一段区间
void build(int u,int l,int r){
tr[u]={l,r};
if(l==r) return;//意味着到达了叶节点
int mid=l+r>>1;
build(u<<1,l,mid);//等于2*u
build(u<<1|1,mid+1,r);//等于2*u+1
//一般后面接上pushup(u)
}
查询,修改
原理:都是依次递归,比较简单,详细见后面例题。
补充:查询最小值(图1),查询区间和(图2)构造的线段树
图1
图2
线段树要开4倍空间
单点修改:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 200010;
int m, p;
struct Node
{
int l, r;
int v; // 区间[l, r]中的最大值
}tr[N * 4];
void pushup(int u) // 由子节点的信息,来计算父节点的信息
{
tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}
void build(int u, int l, int r)
{
tr[u] = {l, r};
if (l == r) return;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
int query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].v; // 树中节点,已经被完全包含在[l, r]中了
int mid = tr[u].l + tr[u].r >> 1;
int v = 0;
if (l <= mid) v = query(u << 1, l, r);
if (r > mid) v = max(v, query(u << 1 | 1, l, r));
return v;
}
void modify(int u, int x, int v)
{
if (tr[u].l == x && tr[u].r == x) tr[u].v = v;
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
}
int main()
{
int n = 0, last = 0;
scanf("%d%d", &m, &p);
build(1, 1, m);
int x;
char op[2];
while (m -- )
{
scanf("%s%d", op, &x);
if (*op == 'Q')
{
last = query(1, n - x + 1, n);
printf("%d\n", last);
}
else
{
modify(1, n + 1, ((LL)last + x) % p);
n ++ ;
}
}
return 0;
}
查询区间最大连续子段和,单点修改
如何知道上面的东西,我们推导一下,首先我们要求一个区间内最大连续子段和。
那么根据上述操作我们发现我们可以求出tmax,但是引入了lmax与rmax,我们再想办法解决这个问题。
而引入的sum只需要求出区间和就可以。
则:pushup代码如下
void pushup(Node &u, Node &l, Node &r)
{
u.sum = l.sum + r.sum;
u.lmax = max(l.lmax, l.sum + r.lmax);
u.rmax = max(r.rmax, r.sum + l.rmax);
u.tmax = max(max(l.tmax, r.tmax), l.rmax + r.lmax);
}
void pushup(int u)
{
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 500010;
int n, m;
int w[N];
struct Node
{
int l, r;
int sum, lmax, rmax, tmax;
}tr[N * 4];
void pushup(Node &u, Node &l, Node &r)
{
u.sum = l.sum + r.sum;
u.lmax = max(l.lmax, l.sum + r.lmax);
u.rmax = max(r.rmax, r.sum + l.rmax);
u.tmax = max(max(l.tmax, r.tmax), l.rmax + r.lmax);
}
void pushup(int u)
{
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r)
{
if (l == r) tr[u] = {l, r, w[r], w[r], w[r], w[r]};
else
{
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int x, int v)
{
if (tr[u].l == x && tr[u].r == x) tr[u] = {x, x, v, v, v, v};
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
}
Node query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u];
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid) return query(u << 1, l, r);
else if (l > mid) return query(u << 1 | 1, l, r);
else
{
auto left = query(u << 1, l, r);
auto right = query(u << 1 | 1, l, r);
Node res;
pushup(res, left, right);
return res;
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
build(1, 1, n);
int k, x, y;
while (m -- )
{
scanf("%d%d%d", &k, &x, &y);
if (k == 1)
{
if (x > y) swap(x, y);
printf("%d\n", query(1, x, y).tmax);
}
else modify(1, x, y);
}
return 0;
}
懒标记
1.Lazy-Tag方法,区间修改
对于区间修改很容易想到解决办法,还是利用线段树的特征:
线段树的节点tree[i]记录了区间i的值,那么可以再定义一个tag[i],用它统一记录区间i的修改,而不是一个个地修改区间内的每个元素,这个方法称为Lazy-Tag(懒惰标记或延迟标记)。
使用Lazy-Tag方法时,若修改的是一个线段区间,就只对这个线段区间进行整体上的
修改,其内部每个元素的内容先不做修改,只有当这个线段区间的一致性被破坏时,才把变
化值传递给下一层的子区间。每次区间修改的复杂度为O(log2n),一共m次操作,总复杂
度为O(mlog2n)。区间i的Lazy操作,用tag[i]记录。
2.push_down
传递函数push_down()是处理Lazy-Tag的一个技巧。在进行多次区间修改时,一个
节点需要记录多个区间修改,而这些区间修改往往有冲突。所以,Lazy-Tag的主要操作是解决多
次区间修改,用push_down()函数完成。首先检查节点p的tag[p],如果有值,说明前面做
区间修改时给p打了tag标记,接下来就把tag[p]传给左右子树,然后把tag[p]清零。
上述操作图示简述:
Struct Node{
int l,r;
int sum,add;
}
Add->懒标记
![](https://i-blog.csdnimg.cn/direct/fc0069d2261f41b9b27417c635c181bf.png)
push_down操作:
对于节点:root,要将root.add把它pushdown一下:
left.add+=root.add
left.sum+=(left.r-left.l+1)*root.add
right.add+=root.add
right.sum+=(right.r-right.l+1)*root.add
root.add=0
![](https://i-blog.csdnimg.cn/direct/f08de53ace964baab724426bec6ef2b0.png)
其他同上
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, m;
int w[N];
struct Node
{
int l, r;
LL sum, add;
}tr[N * 4];
void pushup(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u)
{
auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
if (root.add)
{
left.add += root.add, left.sum += (LL)(left.r - left.l + 1) * root.add;
right.add += root.add, right.sum += (LL)(right.r - right.l + 1) * root.add;
root.add = 0;
}
}
void build(int u, int l, int r)
{
if (l == r) tr[u] = {l, r, w[r], 0};
else
{
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int l, int r, int d)
{
if (tr[u].l >= l && tr[u].r <= r)
{
tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * d;
tr[u].add += d;
}
else // 一定要分裂
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, d);
if (r > mid) modify(u << 1 | 1, l, r, d);
pushup(u);
}
}
LL query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
LL sum = 0;
if (l <= mid) sum = query(u << 1, l, r);
if (r > mid) sum += query(u << 1 | 1, l, r);
return sum;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
build(1, 1, n);
char op[2];
int l, r, d;
while (m -- )
{
scanf("%s%d%d", op, &l, &r);
if (*op == 'C')
{
scanf("%d", &d);
modify(1, l, r, d);
}
else printf("%lld\n", query(1, l, r));
}
return 0;
}
扫描线法
扫描线:
面积并
要求两个矩形叠加后的面积和:
![](https://i-blog.csdnimg.cn/direct/a21d40eedece44848fd3ab78c8688c91.png)
现在假设,扫描线每次会在碰到竖边的时候停下来,如图。
![](https://i-blog.csdnimg.cn/direct/251b5590f2184e3d9f00b91a39e43d7b.png)
为了快速计算出截线段长度,可以将横边赋上不同的权值,具体为:对于一个矩形,其左边权值为1,右边权值为−1。
然后把所有的横边按照x坐标升序排序。这样,对于每个矩形,扫描线总是会先碰到左边,然后再碰到右边。那么就能保证扫描线所截的长度永远非负了。
这样操作以后,就可以和线段树扯上关系。先把所有端点在y轴上离散化(其实就是把所有点的横坐标存到里,然后升序排个序,最后去重)。
为什么会想到用线段树,我们来看一下面积表达式:
我们发现x[0]好求,就是想爱你吨数根节点,关键是,也就是
所对应的矩形另一条边的长度。对于一个矩形,其左边权值为1,右边权值为−1。那么我们发现只要定义一个len表示长度,cnt表示次数,只要cnt激活后,就把len激活到
。
e.g.蓝色表示第一次更新,紫色表示第二次更新,绿色表示第三次更新。
我们发现主要求,而每次激活的区域刚好可以用线段树去统计,很方便。(即区间查询)
(注意离散化)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=100010;
int n;
int x1,x2,y1,y2;
struct Seg{
int x,y1,y2;
int tag;//-1,1
bool operator<(const Seg&t) const{
return x<t.x;
}
}seg[N*2];//区域
typedef long long ll;
struct Node{
int l,r;
ll len,cnt;
}tr[N*8];
vector<int> ys;
void build(int u,int l,int r){
tr[u]={l,r,0,0};
if(l==r) return;
else{
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
}
}
int find(int x){
return lower_bound(ys.begin(), ys.end(), x) - ys.begin();
}
void pushup(int u){
if(tr[u].cnt){
tr[u].len=ys[tr[u].r+1]-ys[tr[u].l];//离散化
}
else if(tr[u].l != tr[u].r)
{
tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
}
else tr[u].len = 0;
}
void modify(int u,int l,int r,int d){
if(l<=tr[u].l&&tr[u].r<=r){
tr[u].cnt+=d;
pushup(u);
}
else{
int mid = tr[u].r + tr[u].l >> 1;
if (l <= mid)modify(u << 1,l,r,d);//左边存在点
if (r > mid)modify(u << 1 | 1,l,r,d);//右边存在点
pushup(u);
}
}
int main(){
scanf("%d",&n);
int j=0;//cnt
for(int i=1;i<=n;i++) {
cin>>x1>>y1>>x2>>y2;
seg[j++]={x1,y1,y2,1};
seg[j++]={x2,y1,y2,-1};
ys.push_back(y1);
ys.push_back(y2);
}
sort(ys.begin(),ys.end());
ys.erase(unique(ys.begin(),ys.end()),ys.end());
sort(seg,seg+j);
build(1,0,ys.size()-2);
ll res=0;
for(int i=0;i<j;i++){
if(i) res+=tr[1].len*(seg[i].x-seg[i-1].x);
modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].tag);
}
cout<<res;
return 0;
}
懒标记迭代
与之前不同,这里这么定义:
struct Node{
int l,r;
ll sum,add,mul;
}tr[N*4];
重点步骤:
推公式:
void pushup(int u){
tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%p;
}
void eval(Node &t,int add,int mul){//懒标记叠加
t.sum = ((ll)t.sum * mul + (ll)(t.r - t.l + 1) * add) % p;
t.mul = (ll)t.mul * mul % p;
t.add = ((ll)t.add * mul + add) % p;
}
void pushdown(int u){
eval(tr[u << 1], tr[u].add, tr[u].mul);
eval(tr[u << 1 | 1], tr[u].add, tr[u].mul);
tr[u].add = 0, tr[u].mul = 1;
}
#include <iostream>
using namespace std;
typedef long long ll;
const int N=100010;
struct Node{
int l,r;
ll sum,add,mul;
}tr[N*4];
int n,p,m;
int w[N];
void pushup(int u){
tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%p;
}
void eval(Node &t,int add,int mul){//懒标记叠加
t.sum = ((ll)t.sum * mul + (ll)(t.r - t.l + 1) * add) % p;
t.mul = (ll)t.mul * mul % p;
t.add = ((ll)t.add * mul + add) % p;
}
void pushdown(int u){
eval(tr[u << 1], tr[u].add, tr[u].mul);
eval(tr[u << 1 | 1], tr[u].add, tr[u].mul);
tr[u].add = 0, tr[u].mul = 1;
}
void build(int u,int l,int r){
if(l==r) tr[u]={l,r,w[r],0,1};
else{
tr[u] = {l, r, 0, 0, 1};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
}
void modify(int u,int l,int r,int add,int mul) {
if (l <= tr[u].l && tr[u].r <= r) {
eval(tr[u], add, mul);
} else {
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, add, mul);
if (r > mid) modify(u << 1 | 1, l, r, add, mul);
pushup(u);
}
}
int query(int u,int l,int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
int sum = 0;
if (l <= mid) sum = query(u << 1, l, r);
if (r > mid) sum = (sum + query(u << 1 | 1, l, r)) % p;
return sum;
}
int main(){
cin>>n>>m>>p;
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
build(1,1,n);
while(m--) {
int op;
cin>>op;
int x,y,k;
switch (op) {
case 1:
cin>>x>>y>>k;
modify(1,x,y,0,k);
break;
case 2:
cin>>x>>y>>k;
modify(1,x,y,k,1);
break;
case 3:
cin>>x>>y;
cout<<query(1,x,y)<<endl;
break;
}
}
return 0;
}