1、线段树是什么?
线段树(Segment Tree)是一种经典的数据结构,它是一颗二叉树,每个节点都代表区间。线段树用于解决静态区间问题和动态区间问题。
它的主要思想是将区间划分成若干个小区间,每个节点代表一个小区间。每个节点的值都是该区间内所有元素的某个函数(如和、最大值、最小值等)的值。在线段树中,每个节点有两个儿子,分别代表该节点所表示区间的左半部分和右半部分。这种表示方法可以在O(logN)的时间内完成区间操作,所以非常适合处理区间问题。
2、如何建立线段树?
对于一个给定的区间[left, right],如果该区间不是叶节点,则将该区间划分为两个区间[mid + 1, right]和[left, mid]。若该区间为叶节点,则将该节点的值赋为该区间的元素值。
void build(int l,int r, int rt){//建立线段树,【l,r】 是当前区间 if(l==r){Sum[rt]=A[l];return;}int m=(l+r)>>1;build(l,m,rt<<1);build(m+1,r,rt<<1|1);pushup(rt);//更新节点信息
}
2.1 如何查询区间操作?
考虑查询区间[begin, end]的和。首先将该区间[left, right]不断地分成两个子区间,直到区间[left, right]完全被包含于[begin, end]内。然后计算该区间内元素的和。
void PushDown(int rt,int ln,int rn){//ln,rn为左子树,右子树的数字数量。 if(Add[rt]){//下推标记 Add[rt<<1]+=Add[rt];Add[rt<<1|1]+=Add[rt];//修改子节点的Sum使之与对应的Add相对应 Sum[rt<<1]+=Add[rt]*ln;Sum[rt<<1|1]+=Add[rt]*rn;//清除本节点标记 Add[rt]=0;}
}int query(int L,int R,int l,int r,int rt){if(L<=l&&r<=R){return Sum[rt];}int m=(l+r)>>1;//下推标记,否则Sum可能不正确PushDown(rt,m-l+1,r-m); int ans=0;if(L<=m)//左子区间与[L,R]有重叠,递归 ans+=query(L,R,l,m,rt<<1);if(R>m)//右子区间与[L,R]有重叠,递归 ans+=query(L,R,m+1,r,rt<<1|1);return ans;
}
2.2 如何更新区间元素?
假设要将区间中第i个元素的值更新为v。首先找到线段树中对应节点,更新节点的值,并递归向上更新所有祖先节点的值。
void update(int num,int c,int l,int r,int rt){//【l,r】 是当前区间,点修改 if(l==r){Sum[rt]+=c;return;}int m=(l+r)>>1;if(num<=m)update(num,c,l,m,rt<<1);else update(num,c,m+1,r,rt<<1|1);pushup(rt);//更新了子节点之后,本节点也要更新
}
接下来,我们通过一个简单的例子来更加深刻地理解线段树的思想。
3、例子
题目描述:给定一个长度为N的序列,支持两种操作:将区间[left, right]中的每个元素加上v,并查询区间[begin, end]的和。
Solution:
建立线段树
因为序列的长度为N,所以形成的线段树的叶节点个数应该为N。因此,在线段树的构造过程中,每个节点要么是叶节点,要么至少有一个儿子。所以,表示线段树的数组的长度应该是4*N。
void buildST(int p, int left, int right) { if (left == right) { //如果该区间为叶节点 ST[p] = A[left]; return; } int mid = (left + right) / 2; buildST(p * 2, left, mid); //建立左子树 buildST(p * 2 + 1, mid + 1, right); //建立右子树 ST[p] = ST[p * 2] + ST[p * 2 + 1]; //计算该节点的值
}
由于ST[p]代表区间[left, right]的和,ST[p * 2]代表区间[left, mid]的和,ST[p * 2 + 1]代表区间[mid + 1, right]的和,因此,ST[p]的值可以直接从ST[p * 2]和ST[p * 2 + 1]的值计算得来,即ST[p] = ST[p * 2] + ST[p * 2 + 1]。
查询区间操作
void queryST(int p, int left, int right, int begin, int end) { if (begin <= left and end >= right) { //如果该区间[left, right]被包含于[begin, end]内 ans += ST[p]; //计算该区间的和 return; } int mid = (left + right) / 2; if (begin <= mid) { queryST(p * 2, left, mid, begin, end); //查询左子树 } if (end > mid) { queryST(p * 2 + 1, mid + 1, right, begin, end); //查询右子树 }
}
更新区间元素
void updateST(int p, int left, int right, int index, int value) { if (left == right) { //找到线段树中对应节点 ST[p] += value; //更新该节点的值 return; } int mid = (left + right) / 2; if (index <= mid) { updateST(p * 2, left, mid, index, value); //更新左子树 } else { updateST(p * 2 + 1, mid + 1, right, index, value); //更新右子树 } ST[p] = ST[p * 2] + ST[p * 2 + 1]; //递归向上更新该节点的祖先节点的值
}
至此,我们可以轻松地解决这个问题了。
4、线段树的应用场景:
-
区间查询:例如查询一个区间内的最大值、最小值、区间和等等。
-
区间修改:当需要修改一个区间中的某些数值时,线段树可以提供高效的修改操作。
-
区间合并:某些问题需要将多个区间进行合并,如区间覆盖或区间合并等问题。
-
高效排序:线段树可以帮助我们快速地对一个区间内的数值进行排序。