长乐(眠)集训DAY7

从前有个小男孩,在机房写博客,结果冲进了一个老师,大喊:都给我滚出去,于是他就不情愿地关掉了网站,回了宿舍。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

 

长乐DAY7,学了线段树LCA倍增

线段树

一种很简单的可以用于区间求和,区间求最值,区间修改等操作的数据结构,一次查询或修改的复杂度为O(logN)。线段树是一种二叉搜索树,可以将一个区间平均分为两个子区间(左右子树),除叶子结点以外,每个节点都有两个子树也就是子区间,每个节点也都存储着一段区间信息[L,R](具体是什么信息还得看题目),比如:区间求和,区间乘法,区间排序,还有各种扩展(luogu蓝题起步,码量++,AC–

对于区间查改需要一个懒标签数组lazytag,来记录添加的内容,在下次修改或者查询时再来更新数组,在一些复杂的情况下,比如区间乘法就可以再加一个标签来记录乘法内容,根据乘法分配律(a+b)*c=a*c+b*c,可以推出pushdown时的转移式。并且在递归式可以使用位运算加速。

一道题要使用线段树应满足可以用两个子区间信息来合并出大区间信息

版题代码(普通区间查改):


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
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int n,m;
LL da[1000001],tree[4000004],tag[4000004];
void build(LL l,LL r,LL q)
{
    if(l==r)
    {
        tree[q]=da[l];
        return;
    }
    LL mid=(l+r)/2;
    build(l,mid,q*2);
    build(mid+1,r,q*2+1);
    tree[q]=tree[q*2]+tree[q*2+1];
}
void pushdown(LL l,LL r,LL q)
{
    if(!tag[q]) return;
    LL mid=(l+r)/2;
    tag[q*2]+=tag[q];
    tree[q*2]+=(mid-l+1)*tag[q];
    tag[q*2+1]+=tag[q];
    tree[q*2+1]+=(r-mid)*tag[q];
    tag[q]=0;
}
void upd(LL l,LL r,LL ql,LL qr,LL v,LL q)
{
    if(qr<l||ql>r)
    {
        return;
    }
    if(l<=ql&&qr<=r)
    {
        tag[q]+=v;
        tree[q]+=v*(qr-ql+1);
        return;
    }
    LL mid=(ql+qr)/2;
    pushdown(ql,qr,q);
    upd(l,r,ql,mid,v,q*2);
    upd(l,r,mid+1,qr,v,q*2+1);
    tree[q]=tree[q*2]+tree[q*2+1];
}
LL query(LL l,LL r,LL ql,LL qr,LL q)
{
    if(qr<l||ql>r)
    {
        return 0;
    }
    if(l<=ql&&qr<=r)
    {
        return tree[q];
    }
    LL mid=(ql+qr)/2;
    pushdown(ql,qr,q);
    return query(l,r,ql,mid,q*2)+query(l,r,mid+1,qr,q*2+1);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&da[i]);
    }
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        LL op,l,r,k;
        scanf("%lld",&op);
        if(op==1)
        {
            scanf("%lld%lld%lld",&l,&r,&k);
            upd(l,r,1,n,k,1);
        }
        else
        {
            scanf("%lld%lld",&l,&r);
            printf("%lld\n",query(l,r,1,n,1));
        }
    }
    return 0;
}

PS:好像还有更快的ZKW线段树,不过看起来好复杂

注:不开了long long见祖坟

LCA

LCA(Lowest Common Ancestors),也就是最近公共祖先最远私人祖坟),百度百科:对于有根树T的两个结点u、v,最近公共祖先LCA(T,u,v)表示一个结点x,满足x是u和v的祖先且x的深度尽可能大。在这里,一个节点也可以是它自己的祖先

一般有四种求法:

1.Tarjan:

是种离线算法,不会

2.树剖:

还是不会

3.ST+RMQ:

不会*3

4.倍增:

终于有个会的了!

永远蒟蒻一枚

思路:用DFS预处理出数组Depth和Dp,Depth表示每个节点深度,Dp[i][j]表示节点i向上跳2^j步所在的节点(倍增的精髓所在),我们可以用Dp(废话)来处理,方程:dp[i][j]=dp[dp[i][j-1]][j-1]。设每次查询时的两个点为u,v,先让跳深度较大的节点使两个节点深度一样(倍增,Dp和Depth数组派上用场),接着两个节点一起跳,如果两个跳完后所在节点一样就不跳,一样就跳,直到跳(还是倍增)不了,这时所在节点的父节点就是它们的LCA。

代码:(有手就行)


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
#include<bits/stdc++.h>
using namespace std;
int n,m;
int k,a[500001],depth[500001],dp[500001][21];
struct node
{
    int now,nex;
} tr[500001*2];
void up(int u,int v)
{  
    k++;
    tr[k].now=v;
    tr[k].nex=a[u];
    a[u]=k;
}
void dfs(int now,int last)
{  
    depth[now]=depth[last]+1;
    dp[now][0]=last;
    for(int i=1; (1<<i)<=depth[now]; i++)
    {
        dp[now][i]=dp[dp[now][i-1]][i-1];
    }
    for(int i=a[now];i!=-1;i=tr[i].nex)
    {
        int v=tr[i].now;
        if(v!=last) dfs(v,now);
    }
}
int query(int u,int v)
{
    if(depth[u]>depth[v])
    {
        swap(u,v);
    }
    for(int i=20; i>=0; i--)
    {
        if(depth[u]<=depth[v]-(1<<i))
        {
            v=dp[v][i];
        }
    }
    if(u==v)
    {
        return u;
    }
    for(int i=20; i>=0; i--)
    {
        if(dp[u][i]==dp[v][i])
        {
            continue;
        }
        else
        {
            u=dp[u][i];
            v=dp[v][i];
        }
    }
    return dp[u][0];
}

int main()
{
    scanf("%d",&n);
    memset(a,-1,sizeof a);
    int u,v;
    for(int i=1; i<=n-1; i++)
    {
        scanf("%d%d",&u,&v);
        up(v,u);
        up(u,v);
    }
    dfs(1,0);
    scanf("%d",&m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&u,&v);
        printf("%d\n",query(u,v));
    }
    return 0;
}

倍增:

是一种加快枚举速度或省略不必要信息的技巧,其正确性的保证来自于二进制唯一分解定理,可以将O(N)的枚举优化为O(logN),比如在一个有序的序列中查找一个数,就可以使用倍增(二分也行,lower_bound()了解一下

 

代码:

无,不想水了

 

 

结尾:

YY:今天学的都是提高组比较重要的算法,明天接着补题

 

这些算法我都学过,所以代码打起来非常快,不过一天照样没A几题(都怪YBTOJ和垃圾一本通,在luoguAC YBT给我RE了,***),调起来真的很坐牢

完,今天的blog就到这了

CMXAKIOI

2022-08-07-23:32:41 upd: wwh还没调出线段树第一题(单点改区间查)

发表评论

邮箱地址不会被公开。 必填项已用*标注