线段树

发表于

image-20210712223119665

线段树构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//PushUp函数更新节点信息，这里以求和为例
void PushUp(int rt)
{
	SegTree[rt].val=SegTree[re<<1].val+SegTree[re<<1|1].val;
}
void build(int l,int r,int rt)
{
	if(l==r)
	{
		SegTree[rt].val=A[l];
		return;
	}
	int m=(l+r)/2;
	build(l,m,rt*2);//递归构造左子树
	build(m+1,r,rt*2+1);//右子树
	PushUp(rt);//回溯，向上更新
}

image-20210715101407315

单点更新（A[l]+=C）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//l,r表示当前节点区间，rt表示当前线段树的根节点编号
void Update(int L,int C,int r,int rt)
{
    if(l==r)
    {
        SegTree[rt].val+=C;
        return;
    }
    int m=(l+r)>>1;
    if(L<=m)Update(L,C,l,m,rt<<1);
    else
        Update(L,C,m+1,r,rt<<1|1);
    PushUp(rt);
}

区间查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
（询问A[L..R]的和)

//[L,R]表示操作区间，[1,r]表示当前区间，rt表示当前节点编号
   int Query(int L,int R,int l,int r,int rt) {
if(L<= l && r<= R)
return SegTree[rt].val;//在区间内直接返回if(L > r llR< 1)
return 0;
int m = ( l + r ) >>1;
int ANS = 0;
if(L<=m)ANS+=Query(L,R,l,m,rt<<1);//左子区间与[L,R]有重叠，递归
if(R>m)ANS+=Query(L,R,m+1,r,rt<<1|1);//右子区间与[L,R]有重叠，递归
    return ANS;
// return Query(L,R,1,m,rt<<1) + Query(L,R,m+1,r,rt<<1| 1);

区间更新

​ image-20210804135448119

image-20210715112856150

image-20210715114503518

A - Balanced Lineup

线段树模板题

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
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
int t,n,q;
long tree1[50010<<2];
long tree2[50010<<2];
long a[50010];
void PushUp(int rt){
    tree1[rt] =max(tree1[rt*2] , tree1[rt*2+1]) ; //区间和的更新操作
    tree2[rt] =min(tree2[rt*2] , tree2[rt*2+1]) ;
}

void Build(int l,int r,int rt){
    // l,r 代表的是这个区间内的左端点 和 右端点， rt代表的是 [l,r] 这个区间内的值是存在哪一个位置的。
    if(l==r){
         tree1[rt] = a[l];
         tree2[rt] = a[l];
        return;
    }
    int m=(l+r)/2;// 对于区间区分，我们一般将m点划入左半边区间
    Build(l,m,rt*2);
    Build(m+1,r,rt*2+1);
    PushUp(rt); // PushUp 函数是通过2个子节点来更新现在这个节点的状态

}
long MAXQuery(int l,int r,int rt,int L,int R){// [L,R]为查询区间
    if(L <= l && r <= R){
        return tree1[rt];// 如果成立则满足查询区间覆盖了当前区间， 直接返回当前区间的值
    }
    int m=(l+r)/2;
    long res=0;
    if(L<=m)    res=max(res,MAXQuery(l,m,rt*2,L,R));//左边有一部分需要查询的区域。
    if(m<R)     res=max(res,MAXQuery(m+1,r,rt*2+1,L,R));//右边有一部分。
    return res;

}
long MINQuery(int l,int r,int rt,int L,int R){// [L,R]为查询区间
    if(L <= l && r <= R){
        return tree2[rt];// 如果成立则满足查询区间覆盖了当前区间， 直接返回当前区间的值
    }
    int m=(l+r)/2;
    long res=0x3f3f3f;
    if(L<=m)    res=min(res,MINQuery(l,m,rt*2,L,R));//左边有一部分需要查询的区域。
    if(m<R)     res=min(res,MINQuery(m+1,r,rt*2+1,L,R));//右边有一部分。
    return res;

}

int main()
{

        scanf("%d%d",&n,&q);
        for(int i = 1; i <= n; i++)
            scanf("%ld", &a[i]);
        Build(1,n,1);
        int a,b;
        while(q--){
            scanf("%d%d",&a,&b);
            cout << MAXQuery(1,n,1,a,b)-MINQuery(1,n,1,a,b) << endl;
        }
    return 0;
}