2020-2021:teams:no_morning_training:shaco:知识点:数据结构:线段树
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:no_morning_training:shaco:知识点:数据结构:线段树 [2020/05/27 18:09] shaco 创建 |
2020-2021:teams:no_morning_training:shaco:知识点:数据结构:线段树 [2020/05/27 18:15] (当前版本) shaco |
||
|---|---|---|---|
| 行 8: | 行 8: | ||
| 二叉树的结构，每一个节点代表一个区间，每个子节点代表父结点区间的一半。 | 二叉树的结构，每一个节点代表一个区间，每个子节点代表父结点区间的一半。 | ||
| 初始版本左儿子下标是父亲下标的两倍，右儿子下标为父亲下标的两倍+1。 | 初始版本左儿子下标是父亲下标的两倍，右儿子下标为父亲下标的两倍+1。 | ||
| - | ==== 操作 ==== | + | ===== 操作 ===== |
| - | === 建树 === | + | （代码源于网上） |
| + | ==== 建树 ==== | ||
| 自上而下，同时更新父节点。 | 自上而下，同时更新父节点。 | ||
| - | ``` | + | <hidden code> |
| + | <code cpp> | ||
| const int maxn = 100005; | const int maxn = 100005; | ||
| int a[maxn],t[maxn<<2]; //a为原来区间，t为线段树 | int a[maxn],t[maxn<<2]; //a为原来区间，t为线段树 | ||
| 行 30: | 行 32: | ||
| } | } | ||
| } | } | ||
| - | ``` | + | </code> |
| - | === 点更新 === | + | </hidden> |
| + | ==== 点更新 ==== | ||
| 自上而下 | 自上而下 | ||
| - | ``` | + | <hidden code> |
| + | <code cpp> | ||
| //递归方式更新 updata(p,v,1,n,1); | //递归方式更新 updata(p,v,1,n,1); | ||
| void updata(int p,int v,int l,int r,int k){ //p为下标，v为要加上的值，l，r为结点区间，k为结点下标 | void updata(int p,int v,int l,int r,int k){ //p为下标，v为要加上的值，l，r为结点区间，k为结点下标 | ||
| 行 47: | 行 51: | ||
| } | } | ||
| } | } | ||
| - | ``` | + | </code> |
| - | === 区间查询 === | + | </hidden> |
| + | ==== 区间查询 ==== | ||
| 自上而下，只统计所查询区间的子区间，在某一个递归进程中查询到则该进程结束。 | 自上而下，只统计所查询区间的子区间，在某一个递归进程中查询到则该进程结束。 | ||
| - | ``` | + | <hidden code> |
| + | <code cpp> | ||
| //递归方式区间查询 query(L,R,1,n,1); | //递归方式区间查询 query(L,R,1,n,1); | ||
| int query(int L,int R,int l,int r,int k){ //[L,R]即为要查询的区间，l，r为结点区间，k为结点下标 | int query(int L,int R,int l,int r,int k){ //[L,R]即为要查询的区间，l，r为结点区间，k为结点下标 | ||
| 行 67: | 行 73: | ||
| } | } | ||
| } | } | ||
| - | ``` | + | </code> |
| - | === 区间更新 === | + | </hidden> |
| + | ==== 区间更新 ==== | ||
| 使用lazy_tag，更新时只下放到最高一层的更新区间的子区间。查询时再更细致地下放。 | 使用lazy_tag，更新时只下放到最高一层的更新区间的子区间。查询时再更细致地下放。 | ||
| - | ``` | + | <hidden code> |
| + | <code cpp> | ||
| void Pushdown(int k){ //更新子树的lazy值，这里是RMQ的函数，要实现区间和等则需要修改函数内容 | void Pushdown(int k){ //更新子树的lazy值，这里是RMQ的函数，要实现区间和等则需要修改函数内容 | ||
| if(lazy[k]){ //如果有lazy标记 | if(lazy[k]){ //如果有lazy标记 | ||
| 行 97: | 行 105: | ||
| } | } | ||
| } | } | ||
| - | ``` | + | </code> |
| + | </hidden> | ||
| + | ===== 例题 ===== | ||
| + | [[https://ac.nowcoder.com/acm/problem/13891|The Trip On Abandoned Railway]] | ||
| + | <hidden mycode> | ||
| + | <code cpp> | ||
| + | #include<cstdio> | ||
| + | #include<cstring> | ||
| + | #define INF 1000000007 | ||
| + | using namespace std; | ||
| + | int t,n,m,d,p[100005],T[500005]; | ||
| + | long long tag[500005][3]; | ||
| + | void push_down(int k) | ||
| + | { | ||
| + | tag[k<<1][0]+=tag[k][0]; | ||
| + | tag[k<<1][1]+=tag[k][1]; | ||
| + | tag[k<<1][2]+=tag[k][2]; | ||
| + | tag[k<<1|1][0]+=tag[k][0]; | ||
| + | tag[k<<1|1][1]+=tag[k][1]; | ||
| + | tag[k<<1|1][2]+=tag[k][2]; | ||
| + | tag[k][0]=tag[k][1]=tag[k][2]=0; | ||
| + | } | ||
| + | void update(int L,int R,int l,int r,int k,int startup,int quota) | ||
| + | { | ||
| + | if(l>=L&&r<=R) | ||
| + | { | ||
| + | tag[k][0]++; | ||
| + | tag[k][1]+=startup; | ||
| + | tag[k][2]+=quota; | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | push_down(k); | ||
| + | int mid=(l+r)/2; | ||
| + | if(L<=mid) | ||
| + | update(L,R,l,mid,k<<1,startup,quota); | ||
| + | if(R>mid) | ||
| + | update(L,R,mid+1,r,k<<1|1,startup,quota); | ||
| + | } | ||
| + | } | ||
| + | int query(int k,int target,int l,int r) | ||
| + | { | ||
| + | if(l==r) | ||
| + | { | ||
| + | int ans=(T[k]+tag[k][2]%INF+((tag[k][0]*l-tag[k][1])*d)%INF)%INF; | ||
| + | T[k]=tag[k][0]=tag[k][1]=tag[k][2]=0; | ||
| + | return ans; | ||
| + | } | ||
| + | push_down(k); | ||
| + | int mid=(l+r)>>1; | ||
| + | if(target<=mid) | ||
| + | return query(k<<1,target,l,mid); | ||
| + | return query(k<<1|1,target,mid+1,r); | ||
| + | } | ||
| + | void build(int now,int l,int r) | ||
| + | { | ||
| + | if(l==r) | ||
| + | T[now]=p[l]; | ||
| + | else | ||
| + | { | ||
| + | int mid=(l+r)>>1; | ||
| + | build(now<<1,l,mid); | ||
| + | build(now<<1|1,mid+1,r); | ||
| + | } | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | scanf("%d",&t); | ||
| + | while(t--) | ||
| + | { | ||
| + | memset(T,0,sizeof(T)); | ||
| + | memset(tag,0,sizeof(tag)); | ||
| + | scanf("%d%d%d",&n,&m,&d); | ||
| + | for(int i=1;i<=n;i++) | ||
| + | scanf("%d",&p[i]); | ||
| + | build(1,1,n); | ||
| + | for(int i=1,op,x,y;i<=m;i++) | ||
| + | { | ||
| + | scanf("%d",&op); | ||
| + | if(op==1) | ||
| + | { | ||
| + | scanf("%d%d",&x,&y); | ||
| + | update(x,n,1,n,1,x,y); | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | scanf("%d",&x); | ||
| + | printf("%d\n",query(1,x,1,n)); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/no_morning_training/shaco/知识点/数据结构/线段树.1590574177.txt.gz · 最后更改: 2020/05/27 18:09 由 shaco
