FS OI
0%

发表于 分类于 ，

Treap（树堆）是一种 OI 常用的平衡树结构，他结合了 BST（二叉查找树）和二叉堆的性质，并通过随机化让平衡树更加平衡，以达到优秀的查找和维护离散数据的效率。

常见的 Treap 写法需要旋转操作来维护平衡树的堆性质，这使得维持树形结构的方式略显复杂，而 FHQ_Treap 则去除了旋转操作，并更加符合平衡树所维护的线性拓扑结构，使得他在极大程度上扩展其功能的同时，代码量极低，这也是其相较于 Splay（伸展树）的优点。

FHQ_Treap 引入了子树的分裂和合并操作，使之在拓扑结构上更加贴近线性表（链表）的结构，而平衡树的快速查找优点也可以保留。据此，FHQ_Treap 还可以更加方便地维护区间信息，同线段树一样，因此线段树的区间类型 FHQ_Treap 都可以兼容。

基本操作：

  • 分裂：将一棵子树从其线性映射的某个位置分成两棵子树。
  • 合并：将两段不同的子树按照线性相连的方式合并成一棵新的子树。

FHQ_Treap 的堆性质的随机关键字是静态的（从该节点被创建起就不会改变），这一点特点更加利于我们在其中维护区间信息和调试。

用 FHQ_Treap 维护简单有序列表——实现 std::set 功能

由于需要维护 BST 和 Heap 的性质，每个节点分配如下资源：

  1. 数据 data：用于维护该位置的信息。
  2. 点权值 pri：用于维护随机化的堆性质。
  3. 左右指针 *ls *rs：用于指向该节点左右节点的资源地址。
  4. 子树大小 size：用于按位置分裂和查询。

观察每棵子树，他们所具有的如下操作都是一致的：

  1. 构造：随机分配点权值，分配该节点的数据，左右子节点的指针。
  2. 分裂：根据需要，可以分为按位置分裂和按值分裂。
  3. 合并：将两棵相邻的子树合并成一棵更大的新子树。

据此，我们可以大致定义出这个子树类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <typename T>
class node {
    T data;
    int pri, size;
    node *ls = NULL, *rs = NULL;

    /* construction */
    node(const T &x) : data(x), size(1), pri(rand()) {}
    
    /* split */
    /* pos */ pair<node*, node*> split(int p);
    /* val */ pair<node*, node*> split(const S &v);

    /* merge */
    static node *merge(node *l, node *r);
}

注意到每次修改之后的子树大小等信息可能会发生改变，因此我们定义一个函数用于处理这些变化：

1
2
3
4
5
void flush() {
    size = 1;
    if(ls) size += ls->size;
    if(rs) size += rs->size;
}

在构造函数中加入 flush() 以更新当前节点的信息。

1
2
/* construction */
node(const T &x) : data(x), pri(rand()) { flush(); }

分裂

按值分裂:

1
2
3
4
5
6
7
8
9
10
11
12
pair<node*,node*> split(const S &v) {
    release();
    if(val <= v) {
        auto split = ls->split(v);
        ls = split.second; flush();
        return {split.first, this};
    } else {
        auto split = rs->split(v);
        rs = split.first; flush();
        return (this, split.second); 
    }
}

按大小分裂：

由于我们在实现这种可以分裂的树的时候不可避免地直接操作指针，因此为了代码简洁和防止非法指针操作，定义函数 get_size 来获取一个指针对应的子树的大小：

1
2
template <typename T>
int get_size(node<T> *x) { return x?x->size:0; }
1
2
3
4
5
6
7
8
9
10
11
12
pair<node*,node*> split(int p) {
    release();
    if(get_size(ls) < p) {
        auto split = ls->split(p);
        ls = split.second; flush();
        return {split.first, this};
    } else {
        auto split = rs->split(p-get_size(ls)-1);
        rs = split.first; flush();
        return (this, split.second); 
    }
}

合并

1
2
3
4
5
6
7
8
9
10
static node *merge(node *l, node *r) {
    if(!l || !r) return (l?l:r);
    if(l->pri > r->pri) {
        l->rs = merge(l->rs,r);
        return l->flush(), l;
    } else {
        r->ls = merge(l,r->ls);
        return r->flush(), r;
    }
}

这样我们就实现了 std::set 的基本功能。

区间维护

FHQ_Treap 的优势主要体现在其区间操作上，我们仿照线段树的定义形式，给这棵平衡树添加区间信息的维护方式。

变更

  1. 添加 seg 信息表示子树对应区间。
  2. 添加 release() recieve() modify() query() 等线段树功能函数。
  3. 在 flush() 中添加对区间信息的维护。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
template <typename S, typename L>
struct node {
    int pri, size;
    S seg, val; L tag;
    node *ls = NULL, *rs = NULL;
    void release() {
        if(ls) ls->recieve(tag);
        if(rs) rs->recieve(tag);
        tag = L();
    }
    void recieve(const L &v) {
        seg.apply(v); val.apply(v);
        tag = L::merge(tag,v);
    }
    void flush() {
        seg = val, size = 1;
        if(ls) seg = S::merge(ls->seg,seg), size += ls->size;
        if(rs) seg = S::merge(seg,rs->seg), size += rs->size;
    }
    static node *merge(node *l, node *r) {
        if(!l || !r) return (l?l:r);
        if(l->pri > r->pri) {
            l->rs = merge(l->rs,r);
            return l->flush(), l;
        } else {
            r->ls = merge(l,r->ls);
            return r->flush(), r;
        }
    }
    void print(string base) {
        if(rs) rs->print(base+"   |");
        cout << base << "---" << val << "-[" << seg << "]-(" << tag << ")-<" << size << ">----{" << pri << "}\n";
        if(ls) ls->print(base+"   |");
    }
    node(const S &x) : pri(rand()), size(1), val(x), tag() { flush(); }
    void modify(int s, int e, const L &v, int _begin = 1) {
        if(s <= _begin && size <= e-_begin+1) { recieve(v); return; }
        release();
        if(ls && s <= get_size(ls)) ls->modify(s,e,v,_begin);
        if(s <= _begin+get_size(ls) && _begin+get_size(ls) <= e) val.apply(v);
        if(rs && e >= _begin+get_size(ls)+1) rs->modify(s,e,v,_begin+get_size(ls)+1);
        flush();
    }
    S query(int s, int e, int _begin = 1) {
        if(s <= _begin && size <= e-_begin+1) return seg;
        release();
        if(ls && s <= get_size(ls) && e > _begin+get_size(ls))
            return S::merge(S::merge(ls->query(s,e,_begin),val),rs->query(s,e,_begin+get_size(ls)));
        if(s <= get_size(ls)) return ls->query(s,e,_begin);
        if(rs && e >= _begin+get_size(ls)+1) return rs->query(s,e,_begin+get_size(ls)+1);
    }
    pair<node*,node*> split(const S &v) {
        release();
        if(val <= v) {
            auto split = ls->split(v);
            ls = split.second; flush();
            return {split.first, this};
        } else {
            auto split = rs->split(v);
            rs = split.first; flush();
            return (this, split.second); 
        }
    }
    pair<node*,node*> split(int p) {
        release();
        if(get_size(ls) < p) {
            auto split = ls->split(p);
            ls = split.second; flush();
            return {split.first, this};
        } else {
            auto split = rs->split(p-get_size(ls)-1);
            rs = split.first; flush();
            return (this, split.second); 
        }
    }
};
template <typename S, typename L>
int get_size(node<S,L> *x) { return x?x->size:0; }

另：FHQ_Treap 显然具备良好的可持久化条件，读者可以思考如何利用已有的代码实现可持久化的数据结构。（提示：可以从指针的变化情况来考虑，不需要修改现在的函数内容就可以实现）

总结

FHQ_Treap 是一种优秀的数据结构，本文探讨了其结构的优秀特征，并探讨了他在区间信息维护上的优势，并提供了代码各部分的解析。

希望本文能够引发读者的思考，并给读者带来关于 FHQ_Treap 的更多理解。

发表于 分类于 ，

读者可能读过我的博客的第一篇文章，其中提到了一种线段树的理解方式，而这篇博客将封装一个 Segment Tree 类，以便于更灵活地使用这种数据结构。

笔者注

本文可能涉及到一些更高级的 C++ 语法和特性，读者可自行查阅：

  • C++ 类的继承
  • 类模板实参推导 (CTAD)
  • 模板类
  • 型别推导和转换
  • 虚函数

以下为我认为不错的文章或文档，在此引用：

腾讯云：[C++] 深入理解面向对象编程特性 : 继承

C语言中文网：C++继承和派生简明教程

API Reference Document：类模板实参推导 (CTAD)(C++17 起)

前段时间我发布的一篇博文重新理解线段树及线段树的应用中提出了一种思维框架，用于更高效地建构线段树算法，在实际情况中，我们可能会遇到更加复杂的多棵树甚至多种树之间嵌套的问题，此时我们对于线段树真正灵活的使用则有了更高的要求。我曾经让 ChatGPT 帮我在原先的代码基础上重新构建一个真正的广泛线段树类，然而由于某些原因，效果难以达到我们的预期。本文中的代码已经解决了这个棘手的问题，并且维持了代码的高可维护性和优美程度，希望读者喜欢。

C++ Code

这里以最简单的线段树应用为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>
using namespace std;

namespace SegmentTree {
    #define mid ((data.l+data.r)>>1)
    template <typename T, typename L, typename SubClass>
    class tree_data {
    public:
        T seg; L tag; int l, r;
    protected:
        tree_data() : l(), r(), seg(), tag() {}
        tree_data(const int &_l, const int &_r) : seg(), tag(), l(_l), r(_r) {}
        static T seg_merge(const T &a, const T &b);
        static L tag_merge(const L &a, const L &b);
        virtual void tag_apply(const L &x) = 0;
    };

    template <typename TD, typename T, typename L>
    class Node {
    private:
        void release() {
            if(ls) ls->recieve(data.tag);
            if(rs) rs->recieve(data.tag);
            data.tag = L();
        }
        void recieve(const L &x) {
            data.tag_apply(x);
            data.tag = TD::tag_merge(data.tag, x);
        }
    public:
        TD data;
        Node *ls, *rs;
        Node(const int &s, const int &e, const T *arr) :
        data(s, e), ls(NULL), rs(NULL) {
            if(data.l == data.r) { data.seg = arr[data.l]; return; }
            ls = new Node(data.l, mid, arr);
            rs = new Node(mid+1, data.r, arr);
            data.seg = TD::seg_merge(ls->data.seg, rs->data.seg);
        }
        Node(const int &s, const int &e) :
        data(s, e), ls(NULL), rs(NULL) {
            if(data.l == data.r) return;
            ls = new Node(data.l, mid);
            rs = new Node(mid+1, data.r);
            data.seg = TD::seg_merge(ls->data.seg, rs->data.seg);
        }
        Node(const Node *base) : data(base->data), ls(base->ls), rs(base->rs) {}
        T query(const int &s, const int &e) {
            if(s <= data.l && data.r <= e) return data.seg;
            release();
            T res = T();
            if(s <= mid) res = TD::seg_merge(res, ls->query(s, e));
            if(e >  mid) res = TD::seg_merge(res, rs->query(s, e));
            return res;
        }
        void modify(const int &s, const int &e, const L &x) {
            if(s <= data.l && data.r <= e) { recieve(x); return; }
            release();
            if(s <= mid) ls->modify(s, e, x);
            if(e >  mid) rs->modify(s, e, x);
            data.seg = TD::seg_merge(ls->data.seg,rs->data.seg);
        }
    //==============================START_DEBUG=================================//
        void Print(string base) {
            cout << base << "---[" << data.l << "," << data.r << "] ";
            data.Print(); cout << "\n";
            if(ls) ls->Print(base+" |");
            if(rs) rs->Print(base+"  ");
        }
    //===============================END_DEBUG==================================//
    };

    template <typename TD>
    class SegTree {
        Node<TD, typename TD::T, typename TD::L> *root;
    public:
        SegTree(const int &s, const int &e, const typename TD::T *arr) :
        root(new Node<TD, typename TD::T, typename TD::L>(s, e, arr)) {}
        SegTree(const int &s, const int &e) :
        root(new Node<TD, typename TD::T, typename TD::L>(s, e)) {}
        typename TD::T query(const int &s, const int &e) { return root->query(s,e); }
        void modify(const int &s, const int &e, const typename TD::L &x) { root->modify(s,e,x); }
    //==============================START_DEBUG=================================//
        void Print() { root->Print(""); }
    //===============================END_DEBUG==================================//
    };
    #undef mid
};

class ADD_SUM_TREE : public SegmentTree::tree_data<int, int, ADD_SUM_TREE> {
public:
    using T = int; using L = int;
    ADD_SUM_TREE(int _l, int _r) : tree_data(_l, _r) {}
    static int seg_merge(const int &a, const int &b) { return a + b; }
    static int tag_merge(const int &a, const int &b) { return a + b; }
    void tag_apply(const int &x) { seg += x * (r - l + 1); }
    //==============================START_DEBUG=================================//
    void Print() { cout << seg << " " << tag; }
    //===============================END_DEBUG==================================//
};

int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int main() {
    SegmentTree::SegTree<ADD_SUM_TREE> tr(1, 9);
    tr.modify(4,9,1);
    tr.Print();
    tr.modify(5,9,2);
    tr.Print();
    cout << tr.query(3,9) << "\n";
    for(int i = 1; i <= 9; ++i) {
        cout << tr.query(i,i) << " ";
    }
    cout << "\n";
    cout << tr.query(3,9) << "\n";
    tr.Print();
    return 0;
}

发表于 分类于 ，

双端链表（双向链表）是一种非常有用的数据结构，但其标准实现通常需要大量的指针操作。这不仅使得代码书写复杂且容易出错，也使得某些算法难以实现。为了简化代码并降低使用双向链表作为基础实现更复杂数据结构的难度，我设计并封装了一个链表类，使其支持通过数组下标方式访问节点。

目标

本项目的目标是实现一个可以使用类似数组下标方式访问链表中第 nn 个元素的双向链表类，并保留链表的所有优良特性。

设计思路

基于普通双向链表，我引入了一个新的管理类，用于管理链表对象。该类包含了三个节点指针（head、tail、cur）和两个用于统计的变量（tot、p），分别用于存储链表总长和当前指针位置的下标。

实现步骤

第一个版本

在第一个版本中，实现了对基本数据类型的支持，主要功能包括：

  • 重载 operator[] 以返回节点类型
  • 为节点类型定义了 insert()、remove()、operator=() 和 operator Type() 等方法

第二个版本

在第二个版本中，添加了对类对象的支持：

  • 引入 NodeProxy 类，用于管理返回对象的行为，并为目标类的子元素重载相关操作符。

注意事项

链表管理类和节点类互相依赖，因此需要使用模板 (template) 来避免未定义行为。

C++ 源代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
using namespace std;

template <typename T>
class Chain {
    template <typename N>
    class Mgr {
    public:
        int tot, p; 
        N *head, *tail, *cur;
        Mgr() {
            head = new N(this);
            tail = new N(this);
            tail->prev = head;
            head->next = tail;
            tot = 0, p = -1, cur = head;
        }
        ~Mgr() {
            while (head->next) {
                head = head->next;
                delete head->prev;
            }
            delete head;
        }
        N* get_node(const int &pos) {
            while (pos >= tot) tail->prev->insert(T());
            const int disHead = pos + 1;
            const int disTail = tot - pos - 1;
            const int disCur = abs(pos - p);
            if (disCur > disHead || disCur > disTail) {
                if (disHead < disTail) p = -1, cur = head;
                else p = tot, cur = tail;
            }
            while (pos < p) p--, cur = cur->prev;
            while (pos > p) p++, cur = cur->next;
            return cur;
        }
        class NodeProxy {
        private: 
            N* node;
        public:
            NodeProxy(N* _node) : node(_node) {}
            T* operator->() { return &(node->data); }
            T& operator*() { return node->data; }
            operator T&() { return node->data; }
            void operator= (const T &_data) { node->data = _data; }
            void insert(const T &_M_data) { node->insert(_M_data); }
            void remove() { node->remove(); }
        };
        NodeProxy operator[](const int &pos) { return NodeProxy(get_node(pos)); }
    };
    class Node {
    public:
        Node *prev, *next; 
        T data; 
        Mgr<Node> *from;
        Node(Mgr<Node> *_from):prev(nullptr), next(nullptr), from(_from) {}
        void insert(const T &_data) {
            from->tot++;
            Node *p = new Node(from);
            p->data = _data;
            p->prev = this;
            p->next = next;
            next->prev = p;
            next = p;
        }
        void remove() {
            from->tot--;
            from->p--;
            from->cur = prev;
            prev->next = next;
            next->prev = prev;
            delete this;
        }
    };
    Mgr<Node> data;
public:
    Chain() {}
    int size() { return data.tot; }
    auto operator[](const int &pos) { return data[pos]; }
};

struct node {
    int x, y;
};

int main() {
    
    Chain<node> c;
    c[10]->y = 9;          // 修改第10个元素的y值
    cout << c[10]->x << " " << c[10]->y << endl; // 输出第10个元素的x和y值
    
    c[9].insert({2, 28}); // 在第9项后插入新的元素
    cout << c[10]->x << " " << c[10]->y << endl; // 输出插入后的第10个元素的x和y值

    c[10].remove();       // 删除第10项
    cout << c[10]->x << " " << c[10]->y << endl; // 输出删除后的第10个元素的x和y值

    Chain<int> ch;

    ch[10] = 100;
    cout << ch[10] << endl;

    ch[9].insert(10);
    cout << (ch[11]>ch[10]?"great\n":"small\n");

    cout << ch[10] << endl;

    ch[10].remove();
    cout << ch[10] << endl;

    return 0;
}

总结

通过这种方式实现的数组式双向链表，不仅保留了链表的灵活性，还使得操作变得更加直观和易于理解。这种设计尤其适用于需要频繁访问或修改特定位置元素的场景。

发表于 分类于 ，

线段树是信息学竞赛（OI）中常见的数据结构，具有 O(nlog⁡2n)O\left(n\log_2n\right) 的区间查询和修改复杂度，适用于维护满足结合律的区间信息。然而，线段树的实现对初学者而言往往较难理解，容易出错且难以调试。这篇文章将介绍一种新的理解方式，简化线段树的概念，有助于更好地理解和应用这一数据结构。

前置概念

线段树的每个节点代表一个连续区间，并具有高度相似性。即使是长度为1的区间，实际上也可以视为一个包含与其他区间相同信息的特殊区间。

线段树的核心在于它能够快速合并相邻两个区间的信息，进而构成更大区间的信息。基于此，我们得出线段树的第一个基本操作：区间合并。

在线段树的区间修改中，通常需要为每种修改方式做特殊处理。在此，提出一个概念：修改信息（或增量信息），用于存储某段区间的变化情况。

有了这个增量信息后，线段树还涉及到另外两个基本操作：修改信息的合并和修改信息的应用。

将这三种基本操作归纳如下：

  1. 区间合并
  2. 修改信息的合并（类似于将两个修改顺序应用的结果进行合并，或者类似群论中的乘法）
  3. 修改信息应用到区间

深入思考

这三种操作是否足以解决复杂的区间问题呢？可以这样考虑：

  • 区间信息可以不只是一个单一的值，还可以是包含向上推导信息的集合（例如矩阵加速的思维方式）。
  • 增量信息同样可以包含多种修改。

这样，我们可以不再为具体问题纠结算法的维护方式，而是通过同一种操作逻辑解决所有问题。

应用实例

例子1:

构建一棵线段树，实现以下三种操作：

  1. 区间求和
  2. 区间内所有数加上 x
  3. 区间内所有数乘上 x

为实现这个需求，需要维护一个 SUM 值（即区间求和信息），增量信息包含 ADD 和 MUL 两个子信息。

由于引入了增量信息的概念，加法和乘法实际上是相同的区间操作，只是它们的 (ADD⁡,MUL⁡)\left(\operatorname{ADD}, \operatorname{MUL}\right) 值不同。加法对应的是 (x,1)\left(x,1\right)，乘法对应的是 (0,x)\left(0,x\right)。

下面是对应的三种基本操作的数学关系：

  1. ∑i=lArAfi+∑i=lBrBfi=∑i=lArBfi⇒SUMA⁡+SUMB⁡=SUMA+B⁡\sum_{i=l_A}^{r_A}f_i + \sum_{i=l_B}^{r_B}f_i = \sum_{i=l_A}^{r_B}f_i \Rightarrow \operatorname{SUM_A} + \operatorname{SUM_B} = \operatorname{SUM_{A+B}}
  2. MULB⁡(MULA⁡n+ADDA⁡)+ADDB⁡=MULA⁡MULB⁡n+MULB⁡ADDA⁡+ADDB⁡\operatorname{MUL_B}\left(\operatorname{MUL_A}n+\operatorname{ADD_A}\right)+\operatorname{ADD_B} = \operatorname{MUL_A}\operatorname{MUL_B}n + \operatorname{MUL_B}\operatorname{ADD_A}+\operatorname{ADD_B}
  3. MUL⁡n+ADD⁡\operatorname{MUL}n + \operatorname{ADD}

原题链接（洛谷）

C++ 实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <bits/stdc++.h>
using namespace std;
template <typename Ty> void read(Ty &x) {
	x = 0; bool f = 0; char c = getchar();
	for(;!isdigit(c);c=getchar()) f = c=='-';
	for(; isdigit(c);c=getchar()) x = x*10+c-'0';
	if(f) x = -x;
}
template <typename Ty, typename ...Ar>
void read(Ty &x, Ar &...y) { read(x); read(y...); }

long long Mod;

template <typename Ty, typename La>
class SegTree {
	private:
	Ty data; La lazy;
	SegTree *ls, *rs;
	int l, r;
	#define mid ((l+r)>>1)
	void release() {
		if(!(bool)lazy) return;
		ls->recieve(lazy);
		rs->recieve(lazy);
		lazy = La();
	}
	void recieve(La v) {
		data = data_modify(data,v);
		if(l==r) return;
		lazy = tag_merge(lazy,v);
	}
	Ty data_modify(const Ty a, const La &v);
	Ty data_merge (const Ty &a, const Ty &b);
	La tag_merge(const La &a, const La &b);
	public:
	SegTree() {}
	SegTree(const int &s, const int &e, const Ty *a) {
		l = s, r = e; lazy = La();
		if(l==r) { data = a[l]; return; }
		ls = new SegTree(l,mid,a);
		rs = new SegTree(mid+1,r,a);
		data = data_merge(ls->data,rs->data);
	}
	Ty query(const int &s, const int &e) {
		release();
		if(s <= l && r <= e) return data;
		Ty res = Ty();
		if(s <= mid) res = data_merge(res,ls->query(s,e));
		if(e >  mid) res = data_merge(res,rs->query(s,e));
		return res;
	}
	void add(const int &s, const int &e, La v) {
		release();
		if(l==r) { data = data_modify(data,v); return; }
		if(s <= l && r <= e) {
			data = data_modify(data,v);
			lazy = tag_merge(lazy,v);
			return;
		}
		if(s <= mid) ls->add(s,e,v);
		if(e >  mid) rs->add(s,e,v);
		data = data_merge(ls->data, rs->data);
	}
	void PrintTree(string legacy) {
		cout << legacy;
		printf("--[%d,%d] ",l,r);
		cout << data <<' ', lazy.print();
		putchar('\n');
		if(l!=r) {
			ls->PrintTree(legacy+" |");
			rs->PrintTree(legacy+"  ");
		}
	}
};
template <typename Ty, typename La>
Ty SegTree<Ty,La>::data_modify(const Ty a, const La &v) {
	return Ty(data*v.mul+v.add*(r-l+1));
}
template <typename Ty, typename La>
Ty SegTree<Ty,La>::data_merge (const Ty &a, const Ty &b) {
	return Ty(a+b);
}
template <typename Ty, typename La>
La SegTree<Ty,La>::tag_merge(const La &a, const La &b) {
	return La(a.add*b.mul+b.add,a.mul*b.mul);
}
struct num {
	int data;
	num() { data = 0; }
	operator int() { return (int)data; }
	template <typename Ty>
	num(const Ty &s) { data = (int)s; }
	template <typename Ty>
	friend num operator+ (num a, Ty b) {
		return num(((long long)a+(long long)b)%Mod);
	}
	template <typename Ty>
	friend num operator* (num a, Ty b) {
		return num(((long long)a*(long long)b)%Mod);
	}
};
struct tag {
	num add, mul;
	tag() { add = 0, mul = 1; }
	tag(const num &a, const num &m) {
		add = a, mul = m;
	}
	operator bool() { return add != 0 || mul != 1; }
	void print() {
		cout << " (" << add << " " << mul << ") ";
	}
};
num arr[100005];

int n, q;
int opt, x, y, k;
int main() {
	read(n, q, Mod);
	for(int i = 1, t; i <= n; ++ i) {
		read(t);
		arr[i] = num(t);
	}
	SegTree<num,tag> tree(1,n,arr);
//	tree.PrintTree("");
	while(q--) {
		read(opt, x, y);
		if(opt == 1) read(k), tree.add(x,y,tag(num(0),num(k)));
		if(opt == 2) read(k), tree.add(x,y,tag(num(k),num(1)));
		if(opt == 3) cout << tree.query(x,y) << '\n';
//		tree.PrintTree("");
	}
	return 0;
}

例子2:

构建一棵线段树，实现以下两种操作：

  1. 将区间内所有数开平方根
  2. 求区间内所有数的和

这里的思路是，如果一段区间完全由1或0构成，则开平方根的新区间不会改变。

原题链接（洛谷）

C++ 实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <bits/stdc++.h>
using namespace std;
template <typename Ty> void read(Ty &x) {
	x = 0; bool f = 0; char c = getchar();
	for(;!isdigit(c);c=getchar()) f = c=='-';
	for(; isdigit(c);c=getchar()) x = x*10+c-'0';
	if(f) x = -x;
}
template <typename Ty, typename ...Ar>
void read(Ty &x, Ar &...y) { read(x); read(y...); }

long long Mod;

template <typename Ty, typename La>
class SegTree {
	private:
	Ty data;
	La lazy;
	SegTree *ls, *rs;
	int l, r;
	#define mid ((l+r)>>1)
	#define leaf (l==r)
	void release() {
		if(!(bool)lazy) return;
		ls->recieve(lazy);
		rs->recieve(lazy);
		lazy = La();
	}
	void recieve(La v) {
		if(leaf) { data = tag_applicate(data,v); return; }
		data = data_predict(data,v);
		lazy = tag_merge(lazy,v);
	}
	Ty data_predict(const Ty a, const La &v) {
		if(a.cnt1+a.cnt0==r-l+1) {
			return Ty(a.cnt1,a.cnt1,a.cnt0);
		}
		ls->add(l,r,v), rs->add(l,r,v);
		lazy = La();
		return data_merge(ls->query(l,r),rs->query(l,r));
	}
	Ty tag_applicate (const Ty &a, const La &b) {
		int t = a.sum;
		for(int i = 0; i < b.sqr; ++ i) t = sqrt(t);
		return Ty(t,(int)t==1,(int)t==0); 
	}
	Ty data_merge (const Ty &a, const Ty &b) {
		return Ty(a.sum+b.sum,a.cnt1+b.cnt1,a.cnt0+b.cnt0);
	}
	La tag_merge(const La &a, const La &b) {
		return La(a.sqr+b.sqr);
	}
	public:
	SegTree() {}
	SegTree(const int &s, const int &e, const Ty *a) {
		l = s, r = e; lazy = La();
		if(leaf) { data = a[l]; return; }
		ls = new SegTree(l,mid,a);
		rs = new SegTree(mid+1,r,a);
		data = data_merge(ls->data,rs->data);
	}
	Ty query(const int &s, const int &e) {
		release();
		if(s <= l && r <= e) return data;
		Ty res = Ty();
		if(s <= mid) res = data_merge(res,ls->query(s,e));
		if(e >  mid) res = data_merge(res,rs->query(s,e));
		return res;
	}
	void add(const int &s, const int &e, La v) {
		release();
		if(leaf) { data = tag_applicate(data,v); return; }
		if(s <= l && r <= e) {
			data = data_predict(data,v);
			lazy = tag_merge(lazy,v);
			return;
		}
		if(s <= mid) ls->add(s,e,v);
		if(e >  mid) rs->add(s,e,v);
		data = data_merge(ls->data, rs->data);
	}
	void PrintTree(string legacy) {
		cout << legacy;
		printf("--[%d,%d] ",l,r);
		printf("%d (%d|%d) [%d]",data.sum, data.cnt0, data.cnt1, lazy.sqr);
		putchar('\n');
		if(!leaf) {
			ls.PrintTree(legacy+" |");
			rs.PrintTree(legacy+"  ");
		}
	}
};
struct data {
	long long sum;
	int cnt1, cnt0;
	data() { sum = cnt1 = cnt0 = 0; }
	data(const long long &s, const int &c1, const int &c0) {
		sum = s, cnt1 = c1, cnt0 = c0;
	}
};
struct tag {
	int sqr;
	tag() { sqr = 0; }
	tag(const int &s) { sqr = s; }
	operator bool() { return false; }
};
int n, m;
int x, l, r;
data arr[100005];
int main() {
	read(n);
	long long t;
	for(int i = 1; i <= n; ++i) read(t),arr[i] = data(t,(int)t==1,(int)t==0);
	read(m);
	SegTree<data,tag> tree(1,n,arr);
	while(m--) {
		read(x,l,r);
		if(x == 1) printf("%lld\n",tree.query(l,r).sum);
		if(x == 2) tree.add(l,r,tag(1));
	}
	return 0;
}

总结

线段树可以视为一种数据框架，根据不同的需求，可以自定义其维护对象和对象之间的行为（即本文提到的三个基本操作），从而将线段树抽象为一种数学模型。这种抽象方式能帮助我们更高效地应对各种区间操作问题。

希望这篇文章能为你带来新的思考和灵感！😊❤️

发表于 更新于

Well, today is my first day to start an online personal blog. So excited!

In my following pages, you can get to know more about me and I would like to share something about coding with every viewer of this site (I hope so).

Anyway, as it was started, it will never ends. Good luck to me.