差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:no_morning_training:shaco:知识点:数据结构:线段树 [2020/05/27 18:11]
shaco
+++ 2020-2021:teams:no_morning_training:shaco:知识点:数据结构:线段树 [2020/05/27 18:15] (当前版本)
shaco
@@ 行 8: / 行 8: @@
 二叉树的结构，每一个节点代表一个区间，每个子节点代表父结点区间的一半。
 初始版本左儿子下标是父亲下标的两倍，右儿子下标为父亲下标的两倍+1。
-==== 操作 ====
+===== 操作 =====
-=== 建树 ===
+（代码源于网上）
+==== 建树 ====
 自上而下，同时更新父节点。
 <hidden code>
@@ 行 33: / 行 34: @@
 </code>
 </hidden>
-=== 点更新 ===
+==== 点更新 ====
 自上而下
 <hidden code>
@@ 行 52: / 行 53: @@
 </code>
 </hidden>
-=== 区间查询 ===
+==== 区间查询 ====
 自上而下，只统计所查询区间的子区间，在某一个递归进程中查询到则该进程结束。
 <hidden code>
@@ 行 74: / 行 75: @@
 </code>
 </hidden>
-=== 区间更新 ===
+==== 区间更新 ====
 使用lazy_tag，更新时只下放到最高一层的更新区间的子区间。查询时再更细致地下放。
 <hidden code>
@@ 行 106: / 行 107: @@
 </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>

CVBB ACM Team

用户工具

站点工具

差别

页面工具