文章目录
有这样一类问题,给定一个数列,让你求某段区间内和。如果对某个值或某段区间内的值进行修改后,如何快速的求和。如果线性执行更新操作或求和操作,无疑时间复杂度太大了。 那么借助分治的思想,在执行更新区间的操作时,把它转化为几段区间的更新,同样求和操作时,也通过维护分段区间的和来达到快速求区间和的问题。线段树就是利用二叉树这种数据结构,来维护区间信息的一种数据结构。
二叉树的每个结点,都代表一段区间。考虑到二叉树的结构,他的根结点就维护从1~n这段区间的信息,根结点的左子树维护1~mid这段区间,右子树维护mid+1~n这段区间,以此递归向下。
一般每个结点需要维护区间修改的信息,以及区间和的信息。
二叉树的叶子结点(从左到右)储存数列的1~n。 修改操作分为两类,一种是在区间的原数值基础上进行修改:加或减去val、乘以val、开根号、、、等;一种是将该区间的值改为val;不同的操作在维护区间和时,相应的有些变化。下面以区间和问题为例,对线段树的实现进行讲解。 如果实现线段树一般需要以下几种操作:
build(start,end,vals) //o(n)
update(index,value) //o(logn)
rangeQuery(start,end) //o(logn+k)
另外线段树可以用结构体指针来索引左右孩子,也可以用数组来存储(申请的长度至少要4n),本文选用前者。
307.Range Sum Query - Mutable 如果做过一些二叉树递归类的题,这个应该就挺好理解了。 几年前我尝试学习线段树的时候,感觉好难。后来刷了一些二叉树类的题,现在再来学习线段树,发现还是挺好理解的。所以如果有些算法学起来困难,可能是前置知识的掌握还不到位。 二叉树的每个结点需要用start、end存储线段起止号,sum存储该段区间的和,另外left、right索引左右子树。 建树过程用buildTree()递归创建就好了,从根节点开始创建,终止条件是线段的start==end(到达叶子节点了,从左到右看就是原数列)。 单点更新:由于是单点更新,所以一定会从根节点往下找,直到相应的叶子节点。然后更新叶子节点。最后还要在回溯的过程中更新每一个包涵该点的线段。 区间查询:对于要查询的区间,如果都被包涵在左子树,就去左子树查询;如果被包涵在右子树,就去右子树查询;如果要查询的区间在左右子树标示的线段中都有一部分,那就分别将左右子树查询的结果加起来。
//线段树是利用二分思想解决区间问题
class SegmentTreeNode{
public:
SegmentTreeNode(int start,int end,int sum,
SegmentTreeNode *left=nullptr,SegmentTreeNode *right=nullptr):
start(start),end(end),sum(sum),left(left),right(right) {}
//禁用赋值构造和拷贝构造函数
SegmentTreeNode(const SegmentTreeNode&)=delete;
SegmentTreeNode& operator=(const SegmentTreeNode&)=delete;
~SegmentTreeNode(){
delete left;
delete right;
left=right=nullptr;
}
public:
int start;
int end;
int sum; //可以是max,min
SegmentTreeNode *left;
SegmentTreeNode *right;
}; //end class SegmentTreeNode
class NumArray {
public:
NumArray(vector<int>& nums) {
nums_.swap(nums);
if(!nums_.empty()){
root_.reset(buildTree(0,nums_.size()-1));
}
}
void update(int i, int val) {
updateTree(root_.get(),i,val-nums_[i]);
}
int sumRange(int i, int j) {
return sumRange(root_.get(),i,j);
}
private:
//创建线段树
SegmentTreeNode *buildTree(int start,int end){
if(start==end){
return new SegmentTreeNode(start,end,nums_[start]);
}
int mid=start+((end-start)>>1);
SegmentTreeNode *left=buildTree(start,mid);
SegmentTreeNode *right=buildTree(mid+1,end);
return new SegmentTreeNode(start,end,left->sum+right->sum,left,right);
}
//更新线段树,将i处的值增加addval
void updateTree(SegmentTreeNode *root,int i,int addval){
if(root->start==i && root->end==i){
root->sum+=addval;
nums_[i]+=addval;
return ;
}
int mid=root->start+((root->end-root->start)>>1);
if(i<=mid){
updateTree(root->left,i,addval);
}else{
updateTree(root->right,i,addval);
}
root->sum+=addval;
}
//计算区间i到j的和
int sumRange(SegmentTreeNode *root,int i,int j){
if(root->start==i && root->end==j){
return root->sum;
}
int mid=root->start+((root->end-root->start)>>1);
if(i>mid){
return sumRange(root->right,i,j);
}else if(j<=mid){
return sumRange(root->left,i,j);
}else{
return sumRange(root->left,i,mid)+sumRange(root->right,mid+1,j);
}
}
/* 打印叶子节点,用于调试
void printTree(SegmentTreeNode *root){
if(root->left==nullptr && root->right==nullptr){
cout<<root->sum<<" ";
return ;
}
printTree(root->left);
printTree(root->right);
}
*/
private:
vector<int> nums_;
std::unique_ptr<SegmentTreeNode> root_;
}; //end class NumArray
hdu 1556 Color the ball 对于这类问题,算法的思想是在区间更新的时候不用全部实施到该区间的每个点上,只将该区间分为几部分,然后实施到分开的几个区间上就好。等到单点查询的时候将单点的值加上所有对该点的更新就好。 由于对区间进行更新,所以二叉树每个节点上需要多一个updateval来维护对区间的更新。 区间更新函数,跟上一类问题中的区间查询有点相似。 单点更新:从根节点向下找到目标点,然后在回溯的时候直接加上每个每个包涵该点的区间维护的updateval。
#include <bits/stdc++.h>
using namespace std;
class SegmentTreeNode{
public:
SegmentTreeNode(int start,int end,int sum,int val=0,SegmentTreeNode *left=nullptr,SegmentTreeNode *right=nullptr):
start(start),end(end),sum(sum),updateval(val),left(left),right(right) {}
//禁用赋值构造和拷贝构造函数
SegmentTreeNode(const SegmentTreeNode&)=delete;
SegmentTreeNode& operator=(const SegmentTreeNode&)=delete;
~SegmentTreeNode(){
delete left;
delete right;
left=right=nullptr;
}
public:
int start;
int end;
int sum; //可以是max,min
int updateval; //用来记录当前区间上update过的数值
SegmentTreeNode *left;
SegmentTreeNode *right;
}; //end class SegmentTreeNode
class NumArray {
public:
NumArray(vector<int>& nums) {
nums_.swap(nums);
if(!nums_.empty()){
root_.reset(buildTree(0,nums_.size()-1));
}
}
void update(int s, int e, int val) {
updateTree(root_.get(),s,e,val);
}
int query(int i) {
return queryTree(root_.get(),i);
}
private:
//创建线段树
SegmentTreeNode *buildTree(int start,int end){
if(start==end){
return new SegmentTreeNode(start,end,nums_[start]);
}
int mid=start+((end-start)>>1);
SegmentTreeNode *left=buildTree(start,mid);
SegmentTreeNode *right=buildTree(mid+1,end);
return new SegmentTreeNode(start,end,left->sum+right->sum,0,left,right);
}
//区间更新线段树,将区间s~e处的值增加addval
void updateTree(SegmentTreeNode *root,int s,int e,int val){
if(root->start==s && root->end==e){
root->updateval+=val;
return ;
}
int mid=root->start+((root->end-root->start)>>1);
if(s>mid){
updateTree(root->right,s,e,val);
}else if(e<=mid){
updateTree(root->left,s,e,val);
}else{
updateTree(root->left,s,mid,val);
updateTree(root->right,mid+1,e,val);
}
}
//单点查询
int queryTree(SegmentTreeNode *root,int i){
if(root->start==i && root->end==i){
return root->sum+root->updateval;
}
int mid=root->start+((root->end-root->start)>>1);
if(i<=mid){
return queryTree(root->left,i)+root->updateval;
}else{
return queryTree(root->right,i)+root->updateval;
}
}
private:
vector<int> nums_;
std::unique_ptr<SegmentTreeNode> root_;
}; //end class NumArray
int main()
{
std::ios::sync_with_stdio(0);
int N;
int a,b;
while(cin>>N){
if(N==0) break;
vector<int> tmp(N+1,0);
NumArray numarry(tmp);
for(int i=0;i<N;i++){
cin>>a>>b;
numarry.update(a,b,1);
}
if(N==1){
cout<<numarry.query(1);
return 0;
}
for(int i=0;i<N;i++){
cout<<numarry.query(i+1);
if(i!=N-1){
cout<<" ";
}else{
cout<<endl;
}
}
}
return 0;
}
以下有两个版本,第一个是pushdown版本。 添加pushdown()后,如果一个数列1~8, 第一次更新1~4,就先将该操作实施到根节点的左孩子上就可以了(有的实现专门用个lazyflag标记,其实不用,如果updateval不为0,则说明lazyflag为1),然后更新根结点的sum。 如果第二次再更新3~4,在向下寻找线段3~4的过程中,要将之前的更新操作往下落实。于是就将1~4上的updateval清零,然后将该更新操作往下分别实施到1~2和3~4上。将寻找3~4的路径上的更新操作都落实到3~4上之后,再执行3~4的更新操作。然后回溯的过程中更新每个结点上的sum。 在查询的时候,如果查询3~3区间,也是需要依次pushdown(),将之前的区间更新落实到3~3区间上,然后返回区间3~3那个结点的sum就可以了。
#include <bits/stdc++.h>
using namespace std;
class SegmentTreeNode{
public:
SegmentTreeNode(int start,int end,long long sum,long long val=0,SegmentTreeNode *left=nullptr,SegmentTreeNode *right=nullptr):
start(start),end(end),sum(sum),updateval(val),left(left),right(right) {}
//禁用赋值构造和拷贝构造函数
SegmentTreeNode(const SegmentTreeNode&)=delete;
SegmentTreeNode& operator=(const SegmentTreeNode&)=delete;
~SegmentTreeNode(){
delete left;
delete right;
left=right=nullptr;
}
public:
int start;
int end;
long long sum; //可以是max,min
long long updateval; //用来记录当前区间上update过的数值
SegmentTreeNode *left;
SegmentTreeNode *right;
}; //end class SegmentTreeNode
class NumArray {
public:
NumArray(vector<long long>& nums) {
nums_.swap(nums);
if(!nums_.empty()){
root_.reset(buildTree(0,nums_.size()-1));
}
}
void update(int s, int e, int val) {
updateTree(root_.get(),s,e,val);
}
long long query(int s,int e) {
return queryTree(root_.get(),s,e);
}
private:
//创建线段树
SegmentTreeNode *buildTree(int start,int end){
if(start==end){
return new SegmentTreeNode(start,end,nums_[start]);
}
int mid=start+((end-start)>>1);
SegmentTreeNode *left=buildTree(start,mid);
SegmentTreeNode *right=buildTree(mid+1,end);
return new SegmentTreeNode(start,end,left->sum+right->sum,0,left,right);
}
//区间更新线段树,将区间s~e处的值增加addval
void updateTree(SegmentTreeNode *root,int s,int e,int val){
if(root->start==s && root->end==e){
root->sum+=val*(e-s+1);
root->updateval+=val;
return ;
}
pushdown(root);
int mid=root->start+((root->end-root->start)>>1);
if(s>mid){
updateTree(root->right,s,e,val);
}else if(e<=mid){
updateTree(root->left,s,e,val);
}else{
updateTree(root->left,s,mid,val);
updateTree(root->right,mid+1,e,val);
}
root->sum=root->left->sum+root->right->sum;
}
//区间查询
long long queryTree(SegmentTreeNode *root,int s,int e){
if(root->start==s && root->end==e){
return root->sum;
}
pushdown(root);
int mid=root->start+((root->end-root->start)>>1);
if(e<=mid){
return queryTree(root->left,s,e);
}else if(s>mid){
return queryTree(root->right,s,e);
}else{
return queryTree(root->left,s,mid)+queryTree(root->right,mid+1,e);
}
}
void pushdown(SegmentTreeNode *root){
if(root->updateval){
root->left->updateval+=root->updateval;
root->right->updateval+=root->updateval;
int mid=root->start+((root->end-root->start)>>1);
root->left->sum+=root->updateval*(mid-root->start+1);
root->right->sum+=root->updateval*(root->end-mid);
root->updateval=0;
}
}
private:
vector<long long> nums_;
std::unique_ptr<SegmentTreeNode> root_;
}; //end class NumArray
int main()
{
std::ios::sync_with_stdio(0);
long long n,m;
long long tmp,oper,x,y,k;
vector<long long> vi;
cin>>n>>m;
vi.resize(n+1);
for(int i=1;i<=n;i++){
cin>>vi[i];
}
NumArray numarry(vi);
for(int i=0;i<m;i++){
cin>>oper;
if(oper==1){
cin>>x>>y>>k;
numarry.update(x,y,k);
}else{
cin>>x>>y;
cout<<numarry.query(x,y)<<endl;
}
}
return 0;
}
标记永久化版本,去掉了pushdown函数,比上一版本有一常数优化。 pushdown版本的是每一次更新区间时,都顺带着将之前的更新向下落实。但是我们其实可以采取”区间更新,单点查询”时的做法,每次更新时实施到相应区间上,不用落实到最下面。然后在每次查询完,回溯的时候,把每个区间上的更新都加上。
#include <bits/stdc++.h>
using namespace std;
class SegmentTreeNode{
public:
SegmentTreeNode(int start,int end,long long sum,long long val=0,SegmentTreeNode *left=nullptr,SegmentTreeNode *right=nullptr):
start(start),end(end),sum(sum),updateval(val),left(left),right(right) {}
//禁用赋值构造和拷贝构造函数
SegmentTreeNode(const SegmentTreeNode&)=delete;
SegmentTreeNode& operator=(const SegmentTreeNode&)=delete;
~SegmentTreeNode(){
delete left;
delete right;
left=right=nullptr;
}
public:
int start;
int end;
long long sum; //可以是max,min
long long updateval; //用来记录当前区间上update过的数值
SegmentTreeNode *left;
SegmentTreeNode *right;
}; //end class SegmentTreeNode
class NumArray {
public:
NumArray(vector<long long>& nums) {
nums_.swap(nums);
if(!nums_.empty()){
root_.reset(buildTree(0,nums_.size()-1));
}
}
void update(int s, int e, int val) {
updateTree(root_.get(),s,e,val);
}
long long query(int s,int e) {
return queryTree(root_.get(),s,e);
}
private:
//创建线段树
SegmentTreeNode *buildTree(int start,int end){
if(start==end){
return new SegmentTreeNode(start,end,nums_[start]);
}
int mid=start+((end-start)>>1);
SegmentTreeNode *left=buildTree(start,mid);
SegmentTreeNode *right=buildTree(mid+1,end);
return new SegmentTreeNode(start,end,left->sum+right->sum,0,left,right);
}
//区间更新线段树,将区间s~e处的值增加addval
void updateTree(SegmentTreeNode *root,int s,int e,int val){
root->sum+=val*(e-s+1); //每次调用该函数,只有整棵线段树的根节点到目标结点的sum值会被更新
if(root->start==s && root->end==e){
root->updateval+=val;
return ;
}
int mid=root->start+((root->end-root->start)>>1);
if(s>mid){
updateTree(root->right,s,e,val);
}else if(e<=mid){
updateTree(root->left,s,e,val);
}else{
updateTree(root->left,s,mid,val);
updateTree(root->right,mid+1,e,val);
}
}
//区间查询
long long queryTree(SegmentTreeNode *root,int s,int e){
if(root->start==s && root->end==e){
return root->sum;
}
int mid=root->start+((root->end-root->start)>>1);
if(e<=mid){
return queryTree(root->left,s,e)+root->updateval*(e-s+1);
}else if(s>mid){
return queryTree(root->right,s,e)+root->updateval*(e-s+1);
}else{
return queryTree(root->left,s,mid)+queryTree(root->right,mid+1,e)+root->updateval*(e-s+1);
}
}
private:
vector<long long> nums_;
std::unique_ptr<SegmentTreeNode> root_;
}; //end class NumArray
int main(){
std::ios::sync_with_stdio(0);
long long n,m;
long long tmp,oper,x,y,k;
vector<long long> vi;
cin>>n>>m;
vi.resize(n+1);
for(int i=1;i<=n;i++){
cin>>vi[i];
}
NumArray numarry(vi);
for(int i=0;i<m;i++){
cin>>oper;
if(oper==1){
cin>>x>>y>>k;
numarry.update(x,y,k);
}else{
cin>>x>>y;
cout<<numarry.query(x,y)<<endl;
}
}
return 0;
}
class SegmentTreeNode2{
public:
SegmentTreeNode2(int start,int end,int max,int min,
SegmentTreeNode2 *left=nullptr,SegmentTreeNode2 *right=nullptr):
start(start),end(end),maxx(max),minn(min),left(left),right(right) {}
//禁用赋值构造和拷贝构造函数
SegmentTreeNode2(const SegmentTreeNode2&)=delete;
SegmentTreeNode2& operator=(const SegmentTreeNode2&)=delete;
~SegmentTreeNode2(){
delete left;
delete right;
left=right=nullptr;
}
public:
int start;
int end;
int maxx;
int minn;
SegmentTreeNode2 *left;
SegmentTreeNode2 *right;
}; //end class SegmentTreeNode2
class NumArray {
public:
NumArray(vector<int>& nums) {
nums_.swap(nums);
if(!nums_.empty()){
root_.reset(buildTree(0,nums_.size()-1));
}
}
int getMax(int i, int j) {
return getMax(root_.get(),i,j);
}
int getMin(int i,int j){
return getMin(root_.get(),i,j);
}
private:
//创建线段树
SegmentTreeNode2 *buildTree(int start,int end){
if(start==end){
return new SegmentTreeNode2(start,end,nums_[start],nums_[start]);
}
int mid=start+((end-start)>>1);
SegmentTreeNode2 *left=buildTree(start,mid);
SegmentTreeNode2 *right=buildTree(mid+1,end);
return new SegmentTreeNode2(start,end,max(left->maxx,right->maxx),min(left->minn,right->minn),left,right);
}
int getMax(SegmentTreeNode2 *root,int i,int j){
if(root->start==i && root->end==j){
return root->maxx;
}
int mid=root->start+((root->end-root->start)>>1);
if(i>mid){
return getMax(root->right,i,j);
}else if(j<=mid){
return getMax(root->left,i,j);
}else{
return max(getMax(root->left,i,mid),getMax(root->right,mid+1,j));
}
}
int getMin(SegmentTreeNode2 *root,int i,int j){
if(root->start==i && root->end==j){
return root->minn;
}
int mid=root->start+((root->end-root->start)>>1);
if(i>mid){
return getMin(root->right,i,j);
}else if(j<=mid){
return getMin(root->left,i,j);
}else{
return min(getMin(root->left,i,mid),getMin(root->right,mid+1,j));
}
}
private:
vector<int> nums_;
std::unique_ptr<SegmentTreeNode2> root_;
}; //end class NumArray
class Solution {
public:
/**
* @param num: array of num
* @param ask: Interval pairs
* @return: return the sum of xor
*/
int Intervalxor(vector<int> &num, vector<vector<int>> &ask) {
// write your code here
NumArray na(num);
int res=na.getMax(ask[0][0]-1,ask[0][1]-1)+na.getMin(ask[0][2]-1,ask[0][3]-1);
for(int i=1;i<ask.size();i++){
res^=(na.getMax(ask[i][0]-1,ask[i][1]-1)+na.getMin(ask[i][2]-1,ask[i][3]-1));
}
return res;
}
};