线段树单点更新

这几天刷了几道关于线段树单点更新的题目,发现单点更新并不像想象中那么简单,有些题目也设计到了数论的知识,本篇文章首先给出模板,然后每道题给出详细的题解(包括一些补充的知识),附有适量的标注。

首先给出一个个人认为比较好改的线段树的模板(基于线段和)

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
//首先定义线段树的结构体。
struct segTree
{
int l,r; //每个tree[k]对应一个节点,其中l,r就是左右区间。
int sum; //每个结点包含的数据是可以根据需要自由定义的,在之后的实现
过程中的区别仅仅是运算方式的不同。
}tree[4*MAXN]; //绝对安全的情况是建议开四倍数据量的大小,当然发现在白书
中的结论是两倍大小(可以举出不安全的例子),在实际运行
中大多数情况三倍也就够了。
void build(int k,int l,int r)
{
tree[k].l=l;
tree[k].r=r;
if(l==r){
tree[k].sum=A[l];
return;
}
int mid=(l+r)/2;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; //可根据题目要求对结点值进
运算结点值。
}
void updata(int k,int pos,int val)
{
if(tree[k].l==tree[k].r)
{
tree[k].sum=val; //这里把最底层叶子结点的值更改为修改后的值,在递归的
过程中会把叶子结点的值自下而上地更新。
return;
}
int mid=(tree[k].l+tree[k].r)/2;
if(pos<mid)
updata(k<<1,pos,val);
else
updata(k<<1|1,pos,val);
tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
}
int query(int k,int l,int r)
{
if(l<=tree[k].l && r>=tree[k].r)
return tree[k].sum;
int m=(tree[k].l+tree[k].r)/2,ret=0;
if(l<=m)
ret+=query(k<<1,l,m);
if(r>m)
ret+=query(k<<1|1,m,r);
return ret;
}

其他的模板还有基于RMQ的,还有记录区间空余位置的(后面的POJ2828与POJ2886),这里不予给出,因为这些都是容易修改得到的。


接下来是个人认为几道不错的例题

SPOJ1043 Can you answer these queries I(利用线段树快速查询字段和)

题意只需要我们查询最大字段和,不涉及查询的操作,所以只需要对我们的updata操作做一些修改,而不需要使用query操作。
最朴素的最大字段和问题大家都用DP做过,但是如果每次操作都进行一次DP的话,因为很多查询的时候涉及重复的区间,其代价的惊人的,大概为O(mn),在以本体的输入量来看是不允许的。
由于最大字段和也是关于区间的题目,学习线段树之后我们自然就会联想到能否应用线段树的特性来解决这道问题呢?
我们可以观察知道如果利用线段树把区间分为若干子区间,假设现在查询的是区间[a,b],其左右孩子结点就是[a,m]和[m+1,b]那么最大子段和便存在以下的几种情况:

  1. 在左孩子结点代表的区间中取到最大值。
  2. 在右孩子结点代表的区间中取得最大值。
  3. 跨越分界点m取得最大值。(又分为左起最大值,右起最大值)

针对这三种情况,我们可以给线段树结点定义这几个数据:

  1. 该段所有数之和sum,参与到左起最大值、右起最大值的计算当中。
  2. 左起最大值lmax。
  3. 右起最大值rmax。
  4. 该段的最大值mmax。
    在计算得出这些值之后,我们便可以根据上面所列的几种情况列式比较递归得出索要查询区间的最大字段和。
    给出代码如下:
    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
    #include <iostream>
    using namespace std;
    int A[50010];
    struct segTree
    {
    int l,r;
    long long sum,lmax,rmax,mmax;
    }tree[50010*4];
    void build(int k,int l,int r)
    {
    tree[k].l=l;
    tree[k].r=r;
    if(l==r){
    tree[k].lmax=tree[k].rmax=tree[k].sum=tree[k].mmax=A[l];
    return;
    }
    int mid=(l+r)/2;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
    tree[k].lmax=max(tree[k<<1].lmax,tree[k<<1].sum+tree[k<<1|1].lmax);
    tree[k].rmax=max(tree[k<<1|1].rmax,tree[k<<1|1].sum+tree[k<<1].rmax);
    tree[k].mmax=max(tree[k<<1].mmax,tree[k<<1|1].mmax);
    tree[k].mmax=max(tree[k].mmax,tree[k<<1].rmax+tree[k<<1|1].lmax);
    }
    long long askr(int k,int l)
    {
    if(tree[k].l==l)
    return tree[k].rmax;
    if(l>=tree[k<<1|1].l)
    return askr(k<<1|1,l);
    return max(tree[k<<1|1].rmax,tree[k<<1|1].sum+askr(k<<1,l));
    }
    long long askl(int k,int r)
    {
    if(tree[k].r==r)
    return tree[k].lmax;
    if(r<=tree[k<<1].r)
    return askl(k<<1,r);
    return max(tree[k<<1].sum+askl(k<<1|1,r),tree[k<<1].lmax);
    }
    long long query(int k,int l,int r)
    {
    if(l==tree[k].l && r==tree[k].r) //这里的query求出来的是在区间中的最大和
    return tree[k].mmax;
    if(l>tree[k<<1].r)
    return query(k<<1|1,l,r);
    if(r<tree[k<<1|1].l)
    return query(k<<1,l,r);
    long long ret=max(query(k<<1,l,tree[k<<1].r),query(k<<1|1,tree[k<<1|1].l,r)); //这里求的是左右起的最大和,
    //和build是一致的
    ret=max(ret,askl(k<<1|1,r)+askr(k<<1,l));
    return ret;
    }
    int main() {
    int num;
    while(cin>>num) {
    for (int i = 1; i <= num; ++i) {
    scanf("%d", &A[i]);
    }
    build(1, 1, num);
    int m;
    int ll, rr;
    cin >> m;
    for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &ll, &rr);
    printf("%lld\n", query(1, ll, rr));
    }
    }
    return 0;
    }

运行的结果:


POJ2828 插队

一开始看见这道题的时候有点懵,为什么适合用线段树做?后来到发现到一个规律,最后一个人插入的次序一定就是他的最终次序,那么就可以利用这点反向推出整个队伍最终的情况,那被挤走的那个人会去哪里呢?题目中我们已经可以知道每个人都会最终插入到一个位置,这个位置必然是他能够插入的第一个空位,正好线段树就可以很方便地查询第k个位置前面的空位数,从而实现插入队列后插入位置的快速决策,所以这道题就转化成为了线段树问题。
比较难处理的一个点就是线段树由上到下的过程中如何转移。一个人插入的时候可以分为几种情况:如果前面的空位数(即左孩子的值)大于他要插入的位置,则可以说明前面存在空位,所以可以向左转移,否则不能满足插入位置pos前面的空位数=pos-1,容易知道这样前面是插入不下他的位置的则pos-左孩子结点的值,继续向下进行直到找到第一个能够插入的空位递归更新线段树即可。
贴代码:

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
#include <iostream>
using namespace std;
int que[2000010];
int pos[2000010],val[2000010];
int id;
struct segTree
{
int l,r;
int sum;
}tree[200010*3];
void build(int k,int l,int r)
{
tree[k].l=l;
tree[k].r=r;
if(l==r){
tree[k].sum=1; //对应到最小的叶子结点代表的就是一个空位。
return;
}
int mid=(l+r)/2;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
}
void updata(int k,int pos)
{
if(tree[k].l==tree[k].r)
{
id=tree[k].l;
tree[k].sum--;
return;
}
if(pos<=tree[k<<1].sum)
updata(k<<1,pos);
else {
pos-=tree[k<<1].sum; //向左时直接插入,向右边的时候就要保证前面留有pos-1个空位,所以要减去前面的空位数.
updata(k<<1|1,pos);
}
tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
}
int main() {
int num;
while(cin>>num){
build(1,1,num);
for(int i=1;i<=num;++i){
scanf("%d%d",&pos[i],&val[i]);
}
for(int i=num;i>=1;--i){
updata(1,pos[i]+1);
que[id]=val[i];
}
printf("%d",que[1]);
for(int i=2;i<=num;++i){
printf(" %d",que[i]);
}
printf("\n");
}
return 0;
}

运行结果:


POJ2828 熊孩子游戏(快速求因子数)

这道题目的题意是每个孩子依次顺时针围成一圈,他们手上都有一张小卡片,从第k个孩子开始出列,出列后亮牌,牌是正数则顺时针(这个时候孩子已经出圈)第k个孩子出列,如果是负数则逆时针第k个孩子出列,游戏直到所有孩子都出圈结束,第K个出队的孩子能够得到F(K)个糖果,F(X)代表这个数的因子数目,那么谁的到的糖果最多?
容易知道的是,出队的操作也涉及区间内空位的快速查询,完全可以照搬上一题的做法,但是困难的地方在于,我们如何快速求出每个数的因子数,而且怎么确定下一个出队的孩子是当前(上一个孩子出队后)第几个孩子呢?
首先引入数论中的一个定理:
对于任意的整型N,分解质因数得到N= P1^x1* P2^x2* …… * Pn^xn;
则N的因子个数M为 M=(x1+1) * (x2+1) * …… *(xn+1)。(Xn为质因子)
由这个定理我们就可以通过一个算法快速地求出x1,x2,…xn的值分别是什么,再相乘我们就可以得到数的因子数表了,下面给出这个算法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void init_factor_table(int n)
{
fill(factor_table,factor_table+n+1,1);
for(int i=2;i<=n;++i)
{
if(factor_table[i]==1)
{
for(int j=i; j<=n ;j+=i)
{
int k=0;
for(int m=j;m%i==0;m/=i,++k);
factor_table[j]*=k+1;
}
}
}
}

接下来我们不再关心孩子的分数,因为它只和他出队的次序有关,而且我们可以做一个预处理来加快程序运行的速度:先对这张表预处理前num(孩子个数)个数,求出最大值是第一个,则我们的updata函数执行几次,记这个最大数对应为第extimes个,如此便可以省去大量不用的updata操作。
那么如何求出当前要出队的孩子是队列中的第几个呢?我们可以推出公式如下: 若是顺时针进行的,则有
k=((k+val[id]-2)%num+num)%num+1;
反之则有:
k=((k+val[id]-2)%num+num)%num+1;
根据C语言的特性,我们可以知道一个数加上模数再取模可以保证最后出来的结果是在正数范围内的,这是一个常用的写法。接下来我们只要进行extimes次updata操作来求出第extimes次执行后出队的孩子是谁即可。
给出代码如下:

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
85
86
87
88
#include <iostream>
using namespace std;
char name[5000010][16];
int val[5000010];
int id;
int factor_table[5000010];
void init_factor_table(int n)
{
fill(factor_table,factor_table+n+1,1);
for(int i=2;i<=n;++i)
{
if(factor_table[i]==1)
{
for(int j=i; j<=n ;j+=i)
{
int k=0;
for(int m=j;m%i==0;m/=i,++k);
factor_table[j]*= k+1;
}
}
}
}
struct segTree
{
int l,r;
int sum;
}tree[500010*3];
void build(int k,int l,int r)
{
tree[k].l=l;
tree[k].r=r;
if(l==r){
tree[k].sum=1;
return;
}
int mid=(l+r)/2;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
}
void updata(int k,int pos)
{
if(tree[k].l==tree[k].r)
{
id=tree[k].l;
tree[k].sum--;
return;
}
if(pos<=tree[k<<1].sum)
updata(k<<1,pos);
else {
pos-=tree[k<<1].sum;
updata(k<<1|1,pos);
}
tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
}
int main() {
int num,k;
while(cin>>num>>k){
init_factor_table(num);
build(1,1,num);
int extimes=0;
int temp=-1;
for(int i=1;i<=num;++i){
if(factor_table[i]>temp){
extimes=i;
temp=factor_table[i];
}
}
for(int i=1;i<=num;++i){
scanf("%s%d",name[i],&val[i]);
}
id=0;
val[id]=0;
for(int i=1;i<=extimes;++i){
if(val[id]>0)
k=((k+val[id]-2)%num+num)%num+1;
else
k=((k+val[id]-1)%num+num)%num+1;
cout<<k<<endl;
updata(1,k);
cout<<name[id]<<endl;
num--;
}
cout<<name[id]<<" "<<factor_table[extimes]<<endl;
}
return 0;
}

运行结果:


总结

线段树是竞赛中常用的数据结构,熟练运用模板并修改在限时的比赛中尤为重要,刚开始做的时候我确实不怎么熟练,所以在草稿纸上模拟了每一步的过程都画出了线段树图,研究线段树转移结点的方向,反复做多了几次空间思维能力有了一定的长进便可以比较轻松地修改线段树的模板了,最近都在刷数据结构的题目,之后碰到经典的题目我还会再更新的,感谢你能够耐心看到这里,欢迎给我留言,指出我写得不好或者不对的地方。