模板-线段树

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

模板

单点修改的线段树

template<typename Avalue, typename Tvalue, // 序列类型，线段树类型
    void (*set)(Tvalue&, Avalue),  // 设置线段树初值
    Tvalue (*op)(Tvalue, Tvalue),    // 线段树合并
    Tvalue (*c)(Tvalue, Tvalue)>    // 线段树修改
struct lazysegment_tree {
    std::vector<Tvalue> tree;
    std::vector<Avalue> array;
    size_t size;

#define LCH id * 2
#define RCH id * 2 + 1

    lazysegment_tree() = default;
    lazysegment_tree(size_t n, std::vector<Avalue>& a)
     : tree((n + 1) << 2), array(a), size(n) {
        build(1, 1, size);
    }

    void build(size_t n, std::vector<Avalue>& a) {
        tree.resize((n + 1) << 2);
        size = n;
        array = a;
        build(1, 1, size);
    }
    void build(int id, int l, int r) {
        if (l == r) {
            set(tree[id], array[l]);
            return;
        }
        int mid = (l + r) >> 1;
        build(LCH, l, mid);
        build(RCH, mid + 1, r);
        tree[id] = op(tree[LCH], tree[RCH]);
    }
    void clear() {
        std::vector<Tvalue> tmp1;
        std::vector<Avalue> tmp3;
        tmp1.swap(tree);
        tmp3.swap(array);
        size = 0;
    }
    void modify(int id, int l, int r, int pos, Tvalue value) {
        if (pos <= l && r <= pos) {
            tree[id] = c(tree[id], value);
            return;
        } 
        int mid = (l + r) >> 1;
        if (pos <= mid) modify(LCH, l ,mid, pos, value);
        if (pos > mid) modify(RCH, mid + 1, r, pos, value);
        tree[id] = op(tree[LCH], tree[RCH]);
    }
    Tvalue query(int id, int l, int r, int pl, int pr) {
        if (pl <= l && r <= pr) {
            return tree[id];
        }
        int mid = (l + r) >> 1;
        if (pr <= mid) return query(LCH, l, mid, pl, pr);
        else if (pl > mid) return query(RCH, mid + 1, r, pl, pr);
        return op(query(LCH, l, mid, pl, pr), query(RCH, mid + 1, r, pl, pr));
    }
    template<bool (*cmp)(Tvalue, Tvalue)>
    int lower_bound(int id, int l, int r, int pl, int pr, Tvalue d) {
        if (pl <= l && r <= pr) {
            int mid = (l + r) >> 1;
            if (!cmp(tree[id], d)) return -1;
            else if (l == r) return l;
            else if (cmp(tree[LCH], d)) return lower_bound<cmp>(LCH, l, mid, pl, pr, d);
            else return lower_bound<cmp>(RCH, mid + 1, r, pl, pr, d);
        }
        int mid = (l + r) >> 1, lans = -1, rans = -1;
        if (pl <= mid) lans = lower_bound<cmp>(LCH, l, mid, pl, pr, d);
        if (pr > mid) rans = lower_bound<cmp>(RCH, mid + 1, r, pl, pr, d);
        return (lans != -1 ? lans : rans);
    }

    void modify(int pos, Tvalue value) {
        modify(1, 1, size, pos, value);
    }
    Tvalue query(int pos) {
        return query(1, 1, size, pos, pos);
    }
    Tvalue query(int left, int right) {
        return query(1, 1, size, left, right);
    }
    template<bool (*cmp)(Tvalue, Tvalue)>
    int lower_bound(int left, int right, Tvalue d) {
        return lower_bound<cmp>(1, 1, size, left, right, d);
    }
};

初始化

// 区间最大值， 单点赋值
using ll = long long;
struct tv{
    ll max;
};
void set(tv& a, ll b) {
    a = { b };
}
tv op(tv a, tv b) {
    return { std::max(a.max, b.max) };
}
tv c(tv a, tv b) {
    return b;
}
bool cmp(tv a, tv b) {
    return a.max >= b.max;
}
// 或者 lazysegment_tree<ll, tv, set, op, c> seg(n, a);
lazysegment_tree<ll, tv, set, op, c> seg;
seg.build(n, a);

模板第一个参数 Avalue, 为序列 a 的值 类型。
第二个参数 Tvalue, 为 线段树值 的类型。
第三个参数void (*set)(Tvalue&, Avalue), 为线段树 赋初始值 的函数指针。
第四个参数Tvalue (*op)(Tvalue, Tvalue), 为线段树 合并两个段 的函数指针。
第五个参数Tvalue (*c)(Tvalue, Tvalue), 为线段树 单点修改 的函数指针。

可以全局创建，之后通过 build(n, a) 来构造线段树，也可以直接通过构造函数来创建局部变量，参数与 build 相同。

通过 clear 可以清空线段树。

修改

modify(pos, value), value 的类型与 线段树值 一致。

查询

返回值为 线段树的值 类型。

query(left, right), 区间查询。

query(pos), 单点查询。

线段树上二分

lower_bound<cmp>(left, right, d), 查找区间中第一个满足条件的下标，不存在得到 -1。

cmp 为函数指针 bool (*cmp)(Tvalue, Tvalue)，查找区间中第一个下标 pos 满足 cmp(a[pos], d) == true。

区间修改线段树

template<typename Avalue, typename Tvalue, typename Tag, // 序列类型，线段树类型， 标记类型
    void (*set)(Tvalue&, Avalue),  // 设置线段树初值
    Tvalue (*op)(Tvalue, Tvalue),   // 线段树合并
    void (*tag)(Tvalue&, Tag&, Tag), // 下传标记
    Tag (*e)()>    // 清空标记(标记初值)
struct lazysegment_tree {
    std::vector<Tvalue> tree;
    std::vector<Tag> lazy;
    std::vector<Avalue> array;
    size_t size;

#define LCH id * 2
#define RCH id * 2 + 1

    lazysegment_tree() = default;
    lazysegment_tree(size_t n, std::vector<Avalue>& a)
     : tree((n + 1) << 2), lazy((n + 1) << 2, e()), array(a), size(n) {
        build(1, 1, size);
    }

    void build(size_t n, std::vector<Avalue>& a) {
        tree.resize((n + 1) << 2);
        lazy.resize((n + 1) << 2, e());
        size = n;
        array = a;
        build(1, 1, size);
    }
    void build(int id, int l, int r) {
        if (l == r) {
            set(tree[id], array[l]);
            return;
        }
        int mid = (l + r) >> 1;
        build(LCH, l, mid);
        build(RCH, mid + 1, r);
        tree[id] = op(tree[LCH], tree[RCH]);
    }
    void clear() {
        std::vector<Tvalue> tmp1;
        std::vector<Tag> tmp2;
        std::vector<Avalue> tmp3;
        tmp1.swap(tree);
        tmp2.swap(lazy);
        tmp3.swap(array);
        size = 0;
    }
    void pushdown(int id) {
        if (lazy[id] == e()) return;
        tag(tree[LCH], lazy[LCH], lazy[id]);
        tag(tree[RCH], lazy[RCH], lazy[id]);
        lazy[id] = e();
    }
    void modify(int id, int l, int r, int pl, int pr, Tag value) {
        if (pl <= l && r <= pr) {
            tag(tree[id], lazy[id], value);
            return;
        } 
        pushdown(id);
        int mid = (l + r) >> 1;
        if (pl <= mid) modify(LCH, l ,mid, pl, pr, value);
        if (pr > mid) modify(RCH, mid + 1, r, pl, pr, value);
        tree[id] = op(tree[LCH], tree[RCH]);
    }
    Tvalue query(int id, int l, int r, int pl, int pr) {
        if (pl <= l && r <= pr) {
            return tree[id];
        }
        pushdown(id);
        int mid = (l + r) >> 1;
        if (pr <= mid) return query(LCH, l, mid, pl, pr);
        else if (pl > mid) return query(RCH, mid + 1, r, pl, pr);
        return op(query(LCH, l, mid, pl, pr), query(RCH, mid + 1, r, pl, pr));
    }
    template<bool (*cmp)(Tvalue, Tvalue)>
    int lower_bound(int id, int l, int r, int pl, int pr, Tvalue d) {
        if (pl <= l && r <= pr) {
            int mid = (l + r) >> 1;
            if (!cmp(tree[id], d)) return -1;
            else if (l == r) return l;
            pushdown(id);
            if (cmp(tree[LCH], d)) return lower_bound<cmp>(LCH, l, mid, pl, pr, d);
            else return lower_bound<cmp>(RCH, mid + 1, r, pl, pr, d);
        }
        pushdown(id);
        int mid = (l + r) >> 1, lans = -1, rans = -1;
        if (pl <= mid) lans = lower_bound<cmp>(LCH, l, mid, pl, pr, d);
        if (pr > mid) rans = lower_bound<cmp>(RCH, mid + 1, r, pl, pr, d);
        return (lans != -1 ? lans : rans);
    }

    void modify(int left, int right, Tag value) {
        modify(1, 1, size, left, right, value);
    }
    Tvalue query(int pos) {
        return query(1, 1, size, pos, pos);
    }
    Tvalue query(int left, int right) {
        return query(1, 1, size, left, right);
    }
    template<bool (*cmp)(Tvalue, Tvalue)>
    int lower_bound(int left, int right, Tvalue d) {
        return lower_bound<cmp>(1, 1, size, left, right, d);
    }
};

初始化

// 区间和， 区间加
using ll = long long;
struct tv{
    ll sum;
    int size;
};
void set(tv& a, ll b) {
    a = { b, 1 };
}
tv op(tv a, tv b) {
    return { a.sum + b.sum, a.size + b.size };
}
void tag(tv& a, ll& b, ll c) {
    if (c == 0) return;
    a.sum += c * a.size;
    b += c;
}
ll e() {
    return 0;
}
// 或者 lazysegment_tree<ll, tv, ll, set, op, tag, e> seg(n, a);
lazysegment_tree<ll, tv, ll, set, op, tag, e> seg;
seg.build(n, a);

模板第一个参数 Avalue, 为序列 a 的值 类型。
第二个参数 Tvalue, 为 线段树值 的类型。
第三个参数 Tag, 为 标记 的类型。
第四个参数void (*set)(Tvalue&, Avalue), 为线段树 赋初始值 的函数指针。
第五个参数Tvalue (*op)(Tvalue, Tvalue), 为线段树 合并两个段 的函数指针。
第六个参数void (*tag)(Tvalue&, Tag&, Tag), 为线段树 设置标记 的函数指针。
第七个参数Tag (*e)(), 为线段树 标记的初始值 的函数指针。

可以全局创建，之后通过 build(n, a) 来构造线段树，也可以直接通过构造函数来创建局部变量，参数与 build 相同。

通过 clear 可以清空线段树。

修改

modify(left, right, value), value 的类型与 标记 一致。

查询

返回值为 线段树的值 类型。

query(left, right), 区间查询。

query(pos), 单点查询。

线段树上二分

lower_bound<cmp>(left, right, d), 查找区间中第一个满足条件的下标，不存在得到 -1。

cmp 为函数指针 bool (*cmp)(Tvalue, Tvalue)，查找区间中第一个下标 pos 满足 cmp(a[pos], d) == true。

其他

P3372 【模板】线段树 1

OI-wiki

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
返回列表

上一篇：学习笔记——Spring简介；Spring搭建步骤；Spring的特性；Spring中getBean三种方式；Spring中的标签

下一篇：学习笔记——Mybatis分页插件

“模板-线段树” 的相关文章

C++11新特性：四种类型转换cast说明1年前 (2023-02-02)
AutoLisp演练(二)1年前 (2023-02-02)
gRPC入门与实操(.NET篇)1年前 (2023-02-02)
【大型软件开发】浅谈大型Qt软件开发（二）面向未来开发——来自未来的技术：COM组件。我如何做到让我们的教学模块像插件一样即插即用，以及为什么这么做。1年前 (2023-02-02)
portswigger 靶场之 XSS 篇(上)1年前 (2023-02-02)
Python实现抽奖程序1年前 (2023-02-02)
AcWing1081. 度的数量1年前 (2023-02-02)
目标文件1年前 (2023-02-02)
JavaScript 数组去重1年前 (2023-02-02)
我总结了写出高质量代码的12条建议1年前 (2023-02-02)

阿里云国际版