线段树入门

Table of Contents

什么是线段树?

线段树,是一种二叉搜索树。它可以把一个从1…N的数组可以用二叉树划分为许多区间,这个区间成为二叉树的节点,使用线段树可以大大加快进行区间操作时的速度,同时,区间的最大值、最小值等问题也可以方便地使用线段树求出。

这里借用一下百度百科中的线段树图片来简要说明一下。

其中,[1,10]是我们的操作区间范围,这个节点作为根节点。

其下有两个子节点,一个是[1,5]一个是[6,10]。

对于每个节点[x,y],当x !=y 时其子节点分别为[x,(x+y)\2]与[(x+y)\2+1,y]

其中,\代表整除

当x == y时,没有子节点,即叶节点。

线段树能做什么?

看到这里,相信很多读者会问,在各个区间的节点上需要保存什么呢?

其实我相信聪明的读者已经看出来了,学过RMQ问题的读者应该已经想到了线段树是一个实现RMQ相比于ST算法占用内存空间更小的算法。实际上正是,例如POJ 2823,用st算法是过不了的。因此,我们还可以在线段树节点上存储区间的最大值、最小值、区间和、区间非0节点数量、区间0节点数量,等等等等。这样,对于一个区间的查询,只需要O(log n)的时间复杂度,相比于O(y-x),快了许多,因而,线段树非常适合解决区间操作的各类问题。

如何建树?

既然线段树本质上是一棵二叉树,因此我们可以按照正常二叉树的建法来建立线段树。通常有两种,一种是指针,一种是4倍叶节点数的数组(3倍和2倍可以被特殊数据卡掉,具体可以自己证明),这里以指针为例,通俗易懂,但数组方式更省内存空间。(毕竟一个指针的大小为内存地址大小,64位中一个指针抵得上两个int的大小了)

这里以一个用于求和的线段树为例

[sourcecode language=”c”]
#include <cstdio>
int input_array[10000];//注意,
struct SegTreeNode {
int l;
int r;
//l和r为区间的范围,其实可以省略,因为查询的时候自然也会计算出来,这里是为了方便调试,通常我们为了省内存空间会去掉
int sum;
SegTreeNode *L;
SegTreeNode *R;
SegTreeNode():l(0),r(0),sum(0),L(NULL),R(NULL){
//特别要注意赋初始值,cyy曾经因为忘了赋上初始值调了一个WA的题目一个小时
}
}root;
void PushUp(SegTreeNode *N) {//根据子节点的值更新父节点的值
if (N->L != NULL) N->sum += N->L->sum;
if (N->R != NULL) N->sum += N->R->sum;
}
void Build_Tree(SegTreeNode *N,int L,int R) {
N->l = L;
N->r = R;
if (L != R) {//叶节点和非叶节点处理方式不同
int mid = (L + R) / 2;//为了方便大多数读者,这里不使用位运算,实际上会卡常数的数据也很少
N->L = new SegTreeNode;
Build_Tree(N->L,L,mid);
N->R = new SegTreeNode;
Build_Tree(N->R,mid+1,R);
PushUp(N);
}
else {
N->sum = input_array[L];
}
}
void Delete_Tree(SegTreeNode *N) {
if (N->L != NULL) Delete_Tree(N->L);
if (N->R != NULL) Delete_Tree(N->R);
delete N;
}
int main() {
int n;
scanf("%d",&n);
for (int i=0;i<n;i++) scanf("%d",&input_array[i]);
Build_Tree(&root,0,n);
//这里使用GDB调试看看节点情况吧!
return 0;
}
[/sourcecode]

区间操作如何实现?

这里我直接引用洛谷上的线段树1模板

[sourcecode language=”c”]
#include <cstdio>
long long N,M;
struct node {
node *l;
node *r;
long long lv;
long long rv;
long long sum;
long long lan;//懒人标记,其下子节点加上的数
node():l(NULL),r(NULL),lv(0),rv(0),sum(0),lan(0){}
}root;
void build_tree(node *n,long long l,long long r) {
n->lv = l;
n->rv = r;
if (l == r) return;
long long mid = (l + r) >> 1;
n->l = new node;
build_tree(n->l,l,mid);
n->r = new node;
build_tree(n->r,mid+1,r);
}
void update(node *n,long long l,long long r,long long v) {
n->sum += v * (r-l+1);
if (n->lv == n->rv) return;
if (l == n->lv && r == n->rv) n->lan += v;
else {
long long mid = (n->lv + n->rv) >> 1;
if (r < mid + 1) update(n->l,l,r,v);
else if (l > mid) update(n->r,l,r,v);
else {
update(n->l,l,mid,v);
update(n->r,mid+1,r,v);
}
}
}
long long query(node *n,long long l,long long r) {
if (n->lv == l && n->rv == r) return n->sum;
else {
long long mid = (n->lv + n->rv) >> 1;
if (r < mid + 1) return n->lan * (r-l+1) + query(n->l,l,r);
else if (l > mid) return n->lan * (r-l+1) + query(n->r,l,r);
else return n->lan * (r-l+1) + query(n->l,l,mid) + query(n->r,mid+1,r);

}
}
int main() {
int N,M;
scanf("%d%d",&N,&M);
build_tree(&root,1,N);
for (int i=1;i<=N;i++) {
long long x;
scanf("%lld",&x);
update(&root,i,i,x);
}
while (M–) {
int o,x,y;
scanf("%d%d%d",&o,&x,&y);
if (o == 1) {//o == 1时代表操作为加
long long k;
scanf("%lld",&k);
update(&root,x,y,k);
}
else {
printf("%lld\n",query(&root,x,y));
}
}
return 0;
}
[/sourcecode]

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to Top