源码:

<线段树算法介绍>

I引子

对于一般的求和的题目,你首先会想到的是:FOR

当然聪明的你,不会眼睁睁看着蒟蒻用暴力的,所用你在用心的教它:前缀和

哎呀,前缀和是一个好东西,查询快的窒息,但聪明的你双目无神炯炯的看着输入格式。

~~将某个数加上x

哇塞~~~~数据君,让数据来的更猛烈吧!

这时,聪明如我的某某某,想到了一种非常遛逼的算法:那就是:线段树!

II思路

树型的结构可以让我们懂得并发现许多东西,接下来我来讲一下什么是线段树。

这个结构具备两种特征:速度快(查询),速度快(修改)

其实它是一种分治算法,把tree[k]分为tree[k乘2]和tree[k乘2+1]

线段树中每一个叶子节点都代表着这些东西:

tree[k]:表示第k个叶子(辅助l,r,等一下我告诉你,存储的时候只用一维k)

l,r:表示l到r的和

必须说明一点,mid是(l+r)/2,左儿子代表的是l到mid,也就是k乘2

右儿子代表mid+1到r,也就是k乘2+1

如图,红色分别为下标和值,黑色是l,r。

k乘2是它的左儿子,k乘2+1是它的右儿子,这很符合o。

都懂了改图,我由三部分进行讲解:

1.make(建造树)

2.change(修改)

3.look(查询)

III做法

1.make

首先我们要建立一颗树。

从树的顶端往下找,到了最下面(叶子结点或叫做需要输入的“时机”)的时候,

你就设置输入,然后它会递归往上,将每一个tree[k]都能加上tree[k乘2]和tree[k乘2]

2.change

改变一片叶子上面的树,其实很简单,跟make没什么区别。

它的思路就是一路往下窜,拿到了最下面,加上所加的数,然后上来,每一个节点都要更新(tree[k]:=tree[k乘2]+tree[k乘2+1])。

3.look

这个思路需要你“意会”与“实践”了,意思是说,你当前的l,r如果可以(注意是可以而不是刚好)套进你要求的l到r的数,那inc(ans,tree[k]);exit(往上再早);

这个exit是点睛之笔,它淋漓尽致的体现了线段树的*速度美*。

IIII代码

1.make

1
2
3
4
5
6
7
8
9
10
11
12
13
14
procedure make(l,r,k:longint);  //make tree
var
        mid:longint;
begin
        if l=r then
        begin
                read(tree[k]);
                exit;
        end;
        mid:=(l+r) div 2;
        make(l,mid,k*2);
        make(mid+1,r,k*2+1);
        inc(tree[k],tree[k*2]+tree[k*2+1]);
end;

2.change

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
procedure change(l,r,k,x,add:longint); //change for tree
var
        mid:longint;
begin
        if l=r then
        begin
                inc(tree[k],add);
                bz:=true;
        end;
        if bz then
exit
        else
        begin
                mid:=(l+r) div 2;
                if x<=mid then
                        change(l,mid,k*2,x,add)
                else
                        change(mid+1,r,k*2+1,x,add);
                tree[k]:=tree[k*2]+tree[k*2+1];
        end;
end;

3.look

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
procedure look(l,r,k,xx,yy:longint); //find answer
var
        mid:longint;
begin
        if (l>=xx)and(r<=yy) then
                inc(find,tree[k])//find为答案
        else
        begin
                mid:=(l+r) div 2;
                if x<=mid then
                        look(l,mid,k*2,xx,yy);
                if y>mid then
                        look(mid+1,r,k*2+1,xx,yy);
        end;
end;

线段树算法的讲解到此结束,希望对你有帮助!