线段树

Vegetableless · 2024-02-04 14:14:47 · 个人记录

发病区

我不会我不会我不会我不会我不会我不会我不会我不会我不会我不会我不会我不会我不会我不会我不会我不会我不会我不会我不会我不会。

怎么调怎么调怎么调怎么调怎么调怎么调怎么调怎么调怎么调怎么调怎么调怎么调怎么调怎么调怎么调怎么调怎么调怎么调怎么调怎么调。

好难写好难写好难写好难写好难写好难写好难写好难写好难写好难写好难写好难写好难写好难写好难写好难写好难写好难写好难写好难写。

关于线段树

来补一发线段树。

首先，我们要知道线段树是什么。用一棵二叉树，来维护一段区间，那么我们可以以 O(n \log n) 的优秀时间复杂度来完成对区间的维护。

当然，如何实现。

首先，摆在我们面前的第一个问题是它的子节点有多少个？

嗯，似乎想不出来。

但是，我们知道，一个二叉树有 2 个子节点（~~这不是废话吗~~），那么完全二叉树的第 n 层就是 2^{n - 1} 个节点，所以说我们要求的实际上是：

2^0 + 2^1 + 2^3 + \cdots + 2^{n - 2} + 2^{n - 1}

嗯，假设我们用的是堆来存，那么每个右子节点都是 2x + 1（设 x 为当前节点的编号），所以实际上为：2^{\lceil n \rceil + 1} - 1，当 2^{n - 1} = 2^x + 1 时，不妨设 a = 2^{n - 1} 那么原式为：

2^{\lceil \log a \rceil + 1} - 1 = 2^{x + 2} - 1 = 4a - 5

那么就是 4 倍空间即可（~~证明得差见谅qwq，从 OI WIKI 上学的加了点自己的想法~~）。

实现

讲了这么多，怎么实现（~~不是讲了吗，建一棵二叉树来维护~~）。

这边建议以 二叉堆 实现的线段树去 OI-WIKI 学捏（即开 4 倍空间的线段树），这里我直接讲动态开点。

动态开点

实际上你在看的时候能一眼看出来之前的空间证明伪了。

因为 2^0 + 2^1 + 2^3 + \cdots + 2^{n - 2} + 2^{n - 1} 这么算出来不应该为 2a - 1 吗？

那是因为会浪费一点点空间。

所以动态开点就出现了，很好理解：

我要的时候开这个点
我不要的时候不开

结束。

回归正题。

这边会给指针版的捏，毕竟你之后也会遇到嘛。

struct SegmentTree{
    SegmentTree *ls , *rs;//存左右儿子

    int l , r , sum , mx;
}sgt[N << 1] , *cnt;//线段树，cnt是指向 sgt 的指针，可以简单理解为存了多少儿子

以上是线段树定义。

cnt = &sgt[0];//这里是让 cnt 指向 sgt 的根节点，你可以也写为 cnt = sgt;

以上是指针初始化。

inline void Build(SegmentTree *pos , int l = 1 , int r = n){//建树
    pos -> l = l , pos -> r = r;

    if(l == r){
        pos -> mx = pos -> sum = a[l];//当前是单个的节点，可以存数组
        return;
    }

    int mid = (l + r) >> 1;

    Build(pos -> ls = ++cnt , l , mid);//建左儿子
    Build(pos -> rs = ++cnt , mid + 1 , r);//建右儿子
    pos -> update();//更新当前节点（update 根据不同题目写法不同）
}

以上是建树。

OK，已经会线段树了，快去做题吧！！！

【模板】线段树 1
【模板】线段树 2
扶苏的问题
XOR的艺术
简单题
三元上升子序列（经典求逆序对 + 维护 dp 数组）
上帝造题的七分钟 2 / 花神游历各国
HH的项链

这边给出两份代码分别为：【模板】线段树 2 和简单题的，分别对应非动态开点和动态开点，同时也对应 区间加/乘 和 区间反转 两种题型。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;

inline int read(){
    register char ch = getchar();
    register int x = 0;
    register bool f = 0;
    while(!isdigit(ch)) f = (ch == '-') , ch = getchar();
    while(isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^  48) , ch = getchar();
    return f ? -x : x;
}

inline void write(int x){
    if(!x) putchar('0');
    if(x < 0) x = -x , putchar('-');

    int w[101] , top = 0;

    while(x)
        w[++top] = x % 10 , x /= 10;

    while(top)
        putchar(w[top] ^ 48) , top--;
    putchar(10);
}

int n , q , mod , multag[4 * N] , addtag[4 * N] , a[N];

struct SegmentTree{
    int l , r , sum;
}sgt[4 * N];

inline void update(int pos){
    sgt[pos].sum = (sgt[pos << 1].sum + sgt[pos << 1 | 1].sum) % mod;
}

inline void build(int pos , int l = 1 , int r = n){
    sgt[pos] = (SegmentTree){l , r};
    multag[pos] = 1;

    if(l == r){
        sgt[pos].sum = a[l] % mod;
        return;
    }

    int mid = (l + r) >> 1;
    build(pos << 1 , l , mid);
    build(pos << 1 | 1 , mid + 1 , r);
    update(pos);
}

inline void pushdown(int pos){
    sgt[pos << 1].sum = (sgt[pos << 1].sum * multag[pos] + addtag[pos] * (sgt[pos << 1].r - sgt[pos << 1].l + 1)) % mod;
    sgt[pos << 1 | 1].sum = (sgt[pos << 1 | 1].sum * multag[pos] + addtag[pos] * (sgt[pos << 1 | 1].r - sgt[pos << 1 | 1].l + 1)) % mod;

    multag[pos << 1] = (multag[pos << 1] * multag[pos]) % mod;
    multag[pos << 1 | 1] = (multag[pos << 1 | 1] * multag[pos]) % mod;

    addtag[pos << 1] = (addtag[pos << 1] * multag[pos] + addtag[pos]) % mod;
    addtag[pos << 1 | 1] = (addtag[pos << 1 | 1] * multag[pos] + addtag[pos]) % mod;

    multag[pos] = 1;
    addtag[pos] = 0;
}

inline void multiply(int pos , int l , int r , int mul){
    if(sgt[pos].l >= l && sgt[pos].r <= r){
        sgt[pos].sum = (sgt[pos].sum * mul) % mod;
        multag[pos] = (multag[pos] * mul) % mod;
        addtag[pos] = (addtag[pos] * mul) % mod;
        return;
    }

    pushdown(pos);

    int mid = (sgt[pos].l + sgt[pos].r) >> 1;
    if(l <= mid) multiply(pos << 1 , l , r , mul);
    if(r > mid) multiply(pos << 1 | 1 , l , r , mul);
    update(pos); 
}

inline void adds(int pos , int l , int r , int add){
    if(sgt[pos].l >= l && sgt[pos].r <= r){
        sgt[pos].sum = (sgt[pos].sum + (sgt[pos].r - sgt[pos].l + 1) * add) % mod;
        addtag[pos] = (addtag[pos] + add) % mod;
        return;
    }

    pushdown(pos);

    int mid = (sgt[pos].l + sgt[pos].r) >> 1;
    if(l <= mid) adds(pos << 1 , l , r , add);
    if(r > mid) adds(pos << 1 | 1 , l , r , add);
    update(pos);
}

inline int query(int pos , int l , int r){
    if(sgt[pos].l >= l && sgt[pos].r <= r) return sgt[pos].sum;

    pushdown(pos);

    int res = 0 , mid = (sgt[pos].l + sgt[pos].r) >> 1;
    if(l <= mid) res = (res + query(pos << 1 , l , r)) % mod;
    if(r > mid) res = (res + query(pos << 1 | 1 , l , r)) % mod;
    return res;
}

signed main(){
    n = read() , q = read() , mod = read();
    for(register int i = 1;i <= n;++i) a[i] = read();

    build(1);

    for(register int i = 1;i <= q;++i){
        int opt = read();
        if(opt == 2){
            int l = read() , r = read() , add = read();
            adds(1 , l , r , add);
        }
        if(opt == 1){
            int l = read() , r = read() , mul = read();
            multiply(1 , l , r , mul);
        }
        if(opt == 3){
            int l = read() , r = read();
            write(query(1 , l , r) % mod);
        }
    }
    return 0;
}//P3373

#include<bits/stdc++.h>
#define lowbit(a) ((a) & -(a))
using namespace std;
const int N = 1e5 + 5;

inline int read(){
    register char ch = getchar();
    register bool f = 0;
    register int x = 0;
    while(!isdigit(ch)) f = (ch == '-') , ch = getchar();
    while(isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48) , ch = getchar();
    return f ? -x : x;
}

int n , m;

struct SegmentTree{
    SegmentTree *ls , *rs;
    int l , r , sum , tag;

    inline void update(){
        sum = ls -> sum + rs -> sum;
    }

    inline void pushdown(){
        if(tag){
            ls -> sum = (ls -> r - ls -> l + 1) - ls -> sum;
            rs -> sum = (rs -> r - rs -> l + 1) - rs -> sum;

            ls -> tag ^= 1;
            rs -> tag ^= 1;

            tag = 0;
        }
    }

    inline void Modify(int L , int R){
        if(L <= l && r <= R){
            sum = (r - l + 1) - sum;
            tag ^= 1;
            return;
        }

        pushdown();

        int mid = (l + r) >> 1;
        if(L <= mid) ls -> Modify(L , R);
        if(R > mid) rs -> Modify(L , R);
        update();
    }

    inline int Query(int P){
        if(l == r) return sum;

        pushdown();

        int mid = (l + r) >> 1 , res = 0;
        if(P <= mid) res |= ls -> Query(P);
        if(P > mid) res |= rs -> Query(P);
        return res; 
    }
}sgt[N << 1] , *cnt;

inline void SegmentTree_Build(SegmentTree *pos , int l = 1 , int r = n){
    pos -> l = l , pos -> r = r;
    pos -> tag = 0;

    if(l == r){
        pos -> sum = 0;
        return;
    }

    int mid = (l + r) >> 1;
    SegmentTree_Build(pos -> ls = ++cnt , l , mid);
    SegmentTree_Build(pos -> rs = ++cnt , mid + 1 , r);
    pos -> update();
}

int main(){
    n = read() , m = read();

    cnt = sgt;

    SegmentTree_Build(sgt);

    for(register int i = 1;i <= m;++i){
        int opt = read();
        if(opt == 1){
            int l = read() , r = read();
            sgt -> Modify(l , r);
        }
        if(opt == 2){
            int p = read();
            int getans = sgt -> Query(p);
            printf("%d\n" , getans);
        }
    }
    return 0;
}//P5057

扫描线

咕咕咕。

线段树合并

咕咕咕。

线段树分裂

咕咕咕。

李超线段树

咕咕咕。

值域线段树

和值域树状数组一样，没什么好讲的。

二维线段树

咕咕咕。

猫树

咕咕咕。

主席树（可持久化线段树）

咕咕咕。