数据结构：线段树

线段树基本知识

线段树=分治法+二叉树结构+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倍空间

链接1

链接2

单点修改：

#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->懒标记

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

【模板】线段树 1 - 洛谷

其他同上

#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;
}

扫描线法

【模板】扫描线 - 洛谷

扫描线：

面积并

要求两个矩形叠加后的面积和：

现在假设，扫描线每次会在碰到竖边的时候停下来，如图。

为了快速计算出截线段长度，可以将横边赋上不同的权值，具体为：对于一个矩形，其左边权值为1，右边权值为−1。

然后把所有的横边按照x坐标升序排序。这样，对于每个矩形，扫描线总是会先碰到左边，然后再碰到右边。那么就能保证扫描线所截的长度永远非负了。

这样操作以后，就可以和线段树扯上关系。先把所有端点在y轴上离散化（其实就是把所有点的横坐标存到里，然后升序排个序，最后去重）。

为什么会想到用线段树，我们来看一下面积表达式：

$\sum_{i=1}^{n}x[0]\cdot l_i$

我们发现x[0]好求，就是想爱你吨数根节点，关键是 $l_i$ ，也就是 $\Delta x_i$ 所对应的矩形另一条边的长度。对于一个矩形，其左边权值为1，右边权值为−1。那么我们发现只要定义一个len表示长度，cnt表示次数，只要cnt激活后，就把len激活到 $l_i$ 。

e.g.蓝色表示第一次更新，紫色表示第二次更新，绿色表示第三次更新。

我们发现主要求 $l_i$ ，而每次激活的区域刚好可以用线段树去统计，很方便。（即区间查询）

（注意离散化）

#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;
}

懒标记迭代

【模板】线段树 2 - 洛谷

与之前不同，这里这么定义：

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;
}