首页 > 其他 > 详细

比较简单的线段树入门

时间:2017-07-18 20:28:07      阅读:231      评论:0      收藏:0      [点我收藏+]

标签:define   需要   时间   char   什么   struct   style   重要   输出格式   

线段树是一种十分方便的数据结构,可以解决多段连续区间的查询问题

对比其他一些数据结构,线段树能够解决的问题是动态的,这也是线段树的特性

线段树的性质还有每个节点保存一个线段,以及左节点保存的线段是父节点保存的线段的左半段,右子节点反之

(即当父节点保存的线段为[1,n],左子节点保存的线段为[1,(1+n)/2],而右子节点保存的线段为[(1+n)/2+1,n])

由于线段树是一颗完全二叉树,所以每个操作的复杂度大概保持在O(log n)

线段树可以做到的操作有如下:

1)构建线段树;

2)区间查询;

3)区间或单点修改;

(单点查询即为左右端点相等的特殊区间查询,单点修改也是同理)

那话不多说(已经不少了),接下来就对以上几种操作举例说明(这里统一以维护区间的和为例)

1)线段树的构建

就是递归构造一个树结构

 1 int a[200010];//a[i]记录数组
 2 struct node{int val;}tree[400010];//tree用于构造线段树
 3 //root 当前父节点
 4 //l 当前节点保存区间的左端点
 5 //r 当前节点保存区间的右端点
 6 void bdt(int root,int l,int r)
 7 {
 8     if(l==r) //当节点保存的区间是一个点时,记录该元素
 9     {tree[root].val=a[l]; return;}
10     //递归构建子树
11     bdt(rt*2,l,(l+r)/2);
12     bdt(rt*2+1,(l+r)/2+1,r);
13     //将左右子节点的值回溯到当前节点上
14     tr[rt].val=tr[rt*2].val+tr[rt*2+1].val;
15 }

 

2)区间查询

区间的查询就是将要查询的区间划分为线段树上节点保存的区间,然后通过节点的合成得到目的区间的值

 1 //root,l,r同上
 2 //f 查询目标区间的左端点
 3 //t 查询目标区间的右端点
 4 int query(int root,int l,int r,int f,int t)
 5 {
 6     //如果查询区间与节点区间没有交集则返回0(0对求和没有影响)
 7     if(t<l || f>r)
 8     return 0;
 9     //如果节点区间包含于查询区间则返回当前区间的求和值
10     if(f<=l && t>=r)
11     return tree[root].val;
12     //左右子树递归将求和保存到父节点
13     return query(root*2,l,(l+r)/2,f,t)+query(root*2+1,(l+r)/2+1,r,f,t);
14 }

 

 可以见得,由于所选的区间尽量少,所以很大程度上节省了时间复杂度,大概节省到了O(log n)

还要记得使用线段树解决问题有一个条件——问题是可以分解解决的

3)单点及区间的修改

首先是单点修改

 1 //root,l,r仍然同上
 2 //k 要修改的点
 3 //add 要增加的值
 4 void update(int root,int l,int r,int k,int add)
 5 {
 6     //当节点是叶子节点执行修改
 7     if(l==r)
 8     {if(k==l) tree[root]+=ad; return;}
 9     //递归左右字数寻找目标节点
10     int mid=(l+r)/2;
11     if(k<=mid)
12     update(root*2,l,mid,k,add);
13     else update(root*2+1,mid+1,r,k,add);
14     //回溯更新父节点(可见回溯在线段树中还是很重要的)
15     tree[root]=tree[root*2]+tree[root*2+1];
16 }

然后是区间修改

区间修改要是也和上面一样那就失去了线段树的意义了(笑

于是就需要一个很有意思的操作——对每个点维护一个延迟标记

这个标记可以记录节点受到了什么样的修改,而这个修改会影响他的子节点

当我们找到一个节点并且判断需要考虑其子节点,就将这个节点的延迟标记向子节点传递,并将这个节点的标记清零

恩...由于这个操作新加入了一个元素,就破坏了以上代码的连续性,这里决定直接上例题(cogs上的一道模板题)

1317. 数列操作c

★★☆   输入文件:shuliec.in   输出文件:shuliec.out   简单对比
时间限制:1 s   内存限制:128 MB

所有答案小于4611686018427387904

【问题描述】

    假设有一列数 {Ai }(1 ≤ i ≤ n),n<=100000 ,支持如下两种操作:

(1)将 A i至A j 的值均增加 D 。( i,j,D 是输入的数)

(2) 输出 A s +A s+1 +…+A t 。( s, t 都是输入的数, S ≤ T )

根据操作要求进行正确操作并输出结果。

【输入格式】

    输入文件第一行一个整数 n ,

第二行为 n 个整数,表示 {A i } 的初始值。

第三行为一个整数 m ,表示操作数

v 下接 m 行,每行描述一个操作,有如下两种情况:

ADD i j d ( 表示将 A i至A j 的值均增加 D , 1<=i,j<=n , d 为整数 )

SUM s t (表示输出 A s +…+A t )

【输出格式】

   对于每一个 SUM 提问,输出结果

【输入输出样例】

输入:

shuliec.in

4

1 4 2 3

3

SUM 1 3

ADD 2 2 50

SUM 2 3

输出:

shuliec.out

7

56

思路:就是一道区间修改区间查询的线段树模板,以下代码

 1 #include<cstdio>
 2 #define LL long long
 3 using namespace std;
 4 int n,m,a[200010];
 5 struct node{LL val,mark;}tree[400010];//这里的mark即为延迟标记
 6 char s[10];
 7 void buildtree(int root,int l,int r)
 8 {
 9     //构建时要先把所有点的延迟标记清零
10     tree[root].mark=0;
11     if(l==r)
12     {tree[root].val=a[l]; return;}
13     buildtree(root*2,l,(l+r)/2);
14     buildtree(root*2+1,(l+r)/2+1,r);
15     tree[root].val=tree[root*2].val+tree[root*2+1].val;
16 }
17 //这就是将延迟标记向下传递的操作
18 void pushdown(int root,int x)
19 {
20     if(tree[root].mark!=0)
21     {
22         //考虑到可能有些节点并不需要继续向下查询,应该是"+="
23         tree[root*2].mark+=tree[root].mark;
24         tree[root*2+1].mark+=tree[root].mark;
25         //这可是个区间啊,每个节点的权值只增加标记值怎么能行
26         tree[root*2].val+=tree[root].mark*(x-(x>>1));
27         tree[root*2+1].val+=tree[root].mark*(x>>1);
28     }tree[root].mark=0;
29 }
30 LL query(int root,int l,int r,int f,int t)
31 {
32     if(t<l || f>r)
33     return 0;
34     if(f<=l && t>=r)
35     return tree[root].val;
36     pushdown(root,r-l+1);
37     return query(root*2,l,(l+r)/2,f,t)+query(root*2+1,(l+r)/2+1,r,f,t);
38 }
39 //备受期待的区间修改,前三个元素仍然是同上
40 //f,t分别是修改区间的左右端点,v则是需要增加的值
41 void add(int root,int l,int r,int f,int t,int v)
42 {
43     int mid=(l+r)/2;
44     //修改区间和节点区间没有交集,自然不考虑
45     if(f>r || t<l) return;
46     //节点区间包含于修改区间,更改区间权值,记录延迟标记
47     if(f<=l && t>=r)
48     {
49         tree[root].mark+=v;
50         tree[root].val+=(LL)v*(r-l+1);
51         return;
52     }
53     //将延迟标记向下传递
54     pushdown(root,(r-l+1));
55     //考虑和左子,右子是否有交集的情况
56     add(root*2,l,mid,f,t,v);
57     add(root*2+1,mid+1,r,f,t,v);
58     //重要的回溯
59     tree[root].val=tree[root*2].val+tree[root*2+1].val;
60 }
61 int main()
62 {
63     int x,y,w,i,j;
64     LL ans;
65     scanf("%d",&n);
66     for(i=1;i<=n;++i)
67     scanf("%d",&a[i]);
68     buildtree(1,1,n);
69     scanf("%d",&m);
70     for(i=1;i<=m;++i)
71     {
72         scanf("%s",s);
73         if(s[0]==S)
74         {
75             scanf("%d%d",&x,&y);
76             ans=query(1,1,n,x,y);
77             printf("%lld\n",ans);
78         }
79         if(s[0]==A)
80         {
81             scanf("%d%d%d",&x,&y,&w);
82             add(1,1,n,x,y,w);
83         }
84     }
85 }

 

比较简单的线段树入门

标签:define   需要   时间   char   什么   struct   style   重要   输出格式   

原文:http://www.cnblogs.com/hntk/p/7197508.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号