当前消息！模板-线段树

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

当前消息！模板-线段树

2023-01-13 23:00:45 来源：博客园

模板

单点修改的线段树

template    // 线段树修改struct lazysegment_tree {    std::vector tree;    std::vector array;    size_t size;#define LCH id * 2#define RCH id * 2 + 1    lazysegment_tree() = default;    lazysegment_tree(size_t n, std::vector& a)     : tree((n + 1) << 2), array(a), size(n) {        build(1, 1, size);    }    void build(size_t n, std::vector& 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 tmp1;        std::vector 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    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(LCH, l, mid, pl, pr, d);            else return lower_bound(RCH, mid + 1, r, pl, pr, d);        }        int mid = (l + r) >> 1, lans = -1, rans = -1;        if (pl <= mid) lans = lower_bound(LCH, l, mid, pl, pr, d);        if (pr > mid) rans = lower_bound(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    int lower_bound(int left, int right, Tvalue d) {        return lower_bound(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 seg(n, a);lazysegment_tree 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(left, right, d), 查找区间中第一个满足条件的下标，不存在得到 -1。

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

区间修改线段树

template    // 清空标记(标记初值)struct lazysegment_tree {    std::vector tree;    std::vector lazy;    std::vector array;    size_t size;#define LCH id * 2#define RCH id * 2 + 1    lazysegment_tree() = default;    lazysegment_tree(size_t n, std::vector& 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& 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 tmp1;        std::vector tmp2;        std::vector 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    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(LCH, l, mid, pl, pr, d);            else return lower_bound(RCH, mid + 1, r, pl, pr, d);        }        pushdown(id);        int mid = (l + r) >> 1, lans = -1, rans = -1;        if (pl <= mid) lans = lower_bound(LCH, l, mid, pl, pr, d);        if (pr > mid) rans = lower_bound(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    int lower_bound(int left, int right, Tvalue d) {        return lower_bound(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 seg(n, a);lazysegment_tree 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可以清空线段树。