通用模板线段树实现

本文受到AtCoder官方库和来写一个像stl一样的线段树的启发

线段树

线段树维护的信息在很多时候可以认为是满足(幺)半群的性质的信息。

一个幺半群 ,其中 为在集合 上定义的二元运算符,幺半群具有以下性质:

  • 封闭性:
  • 结合律:
  • 存在幺元:即 满足 为左幺元;或 为右幺元。

那么我们只需定义 ,就可以实现模版线段树了。

Data 就是定义的 ,+ 就是定义的 ,zero 就是定义的

不过还需要一个 Num,update 和 lazytag 都需要用到 Num

详细说明待更......

1
2
3
4
5
6
7
8
9
10
11
12
struct Num{
ll add;
inline static Num zero(){return {0};}
inline Num operator+(Num b){return {add+b.add};}
};
struct Data{
ll sum,len;
Num lazytag;
inline static Data zero(){return {0,0,Num::zero()};}
inline Data operator+(Num b){return {sum+len*b.add,len,lazytag+b};}
inline Data operator+(Data b){return {sum+b.sum,len+b.len,Num::zero()};}
};
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
template <class Data,class Num>
struct Segment_Tree{
inline void update(int l,int r,Num x){update(1,l,r,x);}
inline Data query(int l,int r){return query(1,l,r);}
Segment_Tree(vector<Data>& a){
n=a.size();
tree.assign(n*4+1,{});
build(a,1,0,n-1);
}
int n;
struct Tree{int l,r;Data data;};
vector<Tree> tree;
inline void pushup(int pos){
tree[pos].data=tree[pos<<1].data+tree[pos<<1|1].data;
}
inline void pushdown(int pos){
tree[pos<<1].data=tree[pos<<1].data+tree[pos].data.lazytag;
tree[pos<<1|1].data=tree[pos<<1|1].data+tree[pos].data.lazytag;
tree[pos].data.lazytag=Num::zero();
}
void build(vector<Data>& a,int pos,int l,int r){
tree[pos].l=l;tree[pos].r=r;
if(l==r){tree[pos].data=a[l];return;}
int mid=(tree[pos].l+tree[pos].r)>>1;
build(a,pos<<1,l,mid);
build(a,pos<<1|1,mid+1,r);
pushup(pos);
}
void update(int pos,int& l,int& r,Num& x){
if(l>tree[pos].r||r<tree[pos].l)return;
if(l<=tree[pos].l&&tree[pos].r<=r){tree[pos].data=tree[pos].data+x;return;}
pushdown(pos);
update(pos<<1,l,r,x);update(pos<<1|1,l,r,x);
pushup(pos);
}
Data query(int pos,int& l,int& r){
if(l>tree[pos].r||r<tree[pos].l)return Data::zero();
if(l<=tree[pos].l&&tree[pos].r<=r)return tree[pos].data;
pushdown(pos);
return query(pos<<1,l,r)+query(pos<<1|1,l,r);
}
};

来看一下最简单的线段树问题【模板】线段树 1

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
struct Num{
ll add;
inline static Num zero(){return {0};}
inline Num operator+(Num b){return {add+b.add};}
};
struct Data{
ll sum,len;
Num lazytag;
inline static Data zero(){return {0,0,Num::zero()};}
inline Data operator+(Num b){return {sum+len*b.add,len,lazytag+b};}
inline Data operator+(Data b){return {sum+b.sum,len+b.len,Num::zero()};}
};
int n,m;
cin>>n>>m;
vector<Data> a(n);
for(auto &i:a){
cin>>i.sum;
i.len=1;
}
Segment_Tree<Data,Num> tree(a);
while(m--){
int op,x,y;
cin>>op>>x>>y;
if(op==1){
int k;
cin>>k;
tree.add(x-1,y-1,{k});
}
else cout<<tree.query(x-1,y-1).sum<<"\n";
}

参考

通用模板线段树实现

http://blog.therehello.top/Segment_Tree/

发布于

2022-04-19

更新于

2022-04-19

许可协议

评论

:D 一言句子获取中...

加载中,最新评论有1分钟缓存...