线段树（裸题）

103 阅读 0 评论 68 点赞

我是靠谱客的博主碧蓝秀发，这篇文章主要介绍线段树（裸题），现在分享给大家，希望可以做个参考。

线段树是什么，先来看道题。

codevs1082 线段树练习3

题目描述 Description

给你N个数，有两种操作：

1：给区间[a,b]的所有数增加X

2：询问区间[a,b]的数的和。

这样一看直接乱搞，然后AC掉......如果这道题数据水可以。但是如果我们要解决数据大的就GG。

其实这是到线段树的裸题，所以我们要使用线段树（其实树状数组也可以，只是我不太擅长）。

那么线段树是一棵二叉树，树中的每一个结点表示了一个区间[a,b]。每一个叶子节点表示了一个单位区间。对于每一个非叶结点所表示的结点[a,b]，其左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。

线段树的看家本领就是区间修改查询，单点修改查询，etc。

那么我们先来看看线段树

1.建树

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void build(int i, int a, int b)
{
    t[i].left = a;
    t[i].right = b;
    t[i].ad = 0;
    if(a == b)
    {
    	t[i].sum = aa[a];
    	return;
	}
    int mid = (a + b) >> 1;
    if(b > a)
    {
    	build(2*i, a, mid);
    	build(2*i+1, mid+1, b);
    }
    t[i].sum = t[2*i].sum + t[2*i+1].sum;
    return ;
}

2.更新

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void updata(int i, int a, int b, int k)
{
    if(t[i].left == a && t[i].right == b)
    {
		t[i].ad += k;
		return ;
	}
    t[i].sum += (b-a+1) * k;
    int mid = (t[i].left + t[i].right) >> 1;
    if(b <= mid)
    	updata(2*i, a, b, k);
    if(a > mid)
    	updata(2*i+1, a, b, k);
    if(b>mid &&a <= mid)
    {
    	updata(2*i, a, mid, k);
    	updata(2*i+1, mid+1, b, k);
	}
    return ;
}

3.查询

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
long long query(int i,int a,int b)
{
    int mid = (t[i].left + t[i].right) >> 1;
    if(t[i].ad && t[i].right != t[i].left)
    {
		updata(2*i, t[i].left, mid, t[i].ad);
		updata(2*i+1, mid+1, t[i].right, t[i].ad);
	}
    t[i].sum += (t[i].right - t[i].left + 1) * t[i].ad;
    t[i].ad = 0;
    if(t[i].left == a && t[i].right == b)
		return t[i].sum;
    t[i].ad = 0;
    if(b <= mid)
		return query(2*i, a, b);
    if(a > mid)
		return query(2*i+1, a, b);
    if(b > mid && a <= mid)
		return query(2*i, a, mid) + qq(2*i+1, mid+1, b);
}