线段树

线段树

概念

线段树是一颗二叉树，二叉树的节点保存着区间信息，跟节点表示1-n，左右子节点分别表示左右各半区间，如图：

由此可以看出，二叉树最后一层有n个节点，所以二叉树的层数为O（logn）这也使得二叉树的查询效率为O（logn），但是最后一层可能不为满二叉树。

应用

对于二叉树的适用范围，由于线段树的高效率查找和修改，所以非常适用于有较大数据量的查询和修改操作的题目，这样可以在很短时间内实现操作而不会因为算法复杂度过高而导致时间超限，除了一般的应用外，线段树也经常和其他的数据结构结合来降得程序运行所要花费的时间，是一种高效的算法。

建树

根据二叉树的性质以及线段树所存储的信息，我们采用递归建树的方式，随着二叉树深度的增加，节点所保存的区间也在缩小，直到最后L==R时，我们就可以更新并返回线段树所维护的信息了。

void build(int node,int L,int R){//递归建树
	if(L==R){//当L==R时到达叶子节点，更新信息并返回
		tree[node]=arr[L];
		return;
	}
	int mid=(L+R)>>1;//区间减半，拆分为左右
	build(node<<1,L,mid);//左子树的建立
	build(node<<1|1,mid+1,R);//右子树的建立
	tree[node]=tree[node<<1]+tree[node<<1|1];//更新当前值
	return;
}

单点修改

对于单点修改，我们只需要查找到要修改的点之后更新区间值即可

void update(int node int L,int R,int k,int v){//单点更新
	if(L==R&&L==k){//判断是否到达要更新的点
		tree[node]+=v;
		return;
	}
	int mid=(L+R)>>1;//区间折半
	if(mid>=k) update(node<<1,L,mid,k,v);//判断要修改的点是否在左区间
	else update(node<<1|1,mid+1,R,k,v);//判断要修改的点是否在右区间
	tree[node]=tree[node<<1]+tree[node<<1|1];//更新区间值
	return;
}

区间修改

对于区间修改，我们需要一个“懒人标记”用来维护线段树，但我们需要修改x-y区间的值时，我们递归搜索区间，如果区间落在x-y之间，我们就对此时的节点做修改标记，同时，更新此处的值返回，我们不需要搜索到叶子节点才修改，那样会影响效率，对于这个懒人标记，当我们对区间做查询的时候，就会起到标记作用，从而保证数据的正确性。

void Add(int node,int L,int R,int v){//区间更新
	lazy[node]+=v;//懒人标记
	tree[node]+=(R-L+1)*v;//区间值修改
	return;
}

void pushdown(int node,int L,int R){//标记下移
	if(lazy[node]==0) return;//没有标记，返回
	int mid=(L+R)>>1;
	Add(node<<1,L,mid,lazy[node]);//左区间标记和值更新
	Add(node<<1|1,mid+1,R,lazy[node]);//右区间标记和值更新
	lazy[node]=0;//此处标记归零
	return;
}

//区间更新
void update_range(int node,int L,int R,int x,int y,int v){
	if(L>=x&&R<=y){//如果当前区间位于修改区间内，则修改
		Add(node,L,R,v);//区间值修改
		return;
	}
	int mid=(L+R)>>1;
	pushdown(node,L,R);//标记下移
	if(x<=mid) update_range(node<<1,L,mid,x,y,v);//搜索左半区间
	if(y>mid) update_range(node<<1|1,mid+1,R,x,y,v);//搜索右半区间
	tree[node]=tree[node<<1]+tree[node<<1|1];//更新区间值
	return;
}

询问

区间询问（for单点修改）

对于询问我们通过递归搜索符合条件区间，并将这些区间的值求和。

int ask(int node,int L,int R,int x,int y){
	if(L>=x&&R<=y){//如果区间位于询问区间，返回当前区间值
		return tree[node];
	}
	int mid=(L+R)>>1;
	int ans=0;
	if(x<=mid) ans+=ask(node<<1,L,mid,x,y);//判断区间是否在询问区间内，并加上区间结果
	if(y>mid) ans+=ask(node<<1|1,mid+1,R,x,y);
	return ans;
}

区间询问（for区间修改）

对于区间修改的询问，我们只需要注意“懒人标记”的下移就好。

int query(int node,int L,int R,int x,int y){
	if(L>=x&&R<=y)//当前区间位于查询区间内
		return tree[node];//返回区间值
	int mid=(L+R)>>1;
	int ans=0;
	pushdown(node,L,R);//标记下移
	if(x<=mid) ans+=query(node<<1,L,mid,x,y);
	if(y>mid) ans+=query(node<<1|1,mid+1,R,x,y);
	return ans;
}

模板

/**********************************************************
* @Author: 			   Maple
* @Date:   			   2020-02-28 11:52:49
* @Last Modified by:   Maple
* @Last Modified time: 2020-02-28 13:55:18
* @Remark: 
**********************************************************/
#include <bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define CSE(x,y) memset(x,y,sizeof(x))
#define INF 0x3f3f3f3f
#define Abs(x) (x>=0?x:(-x))
#define FAST ios::sync_with_stdio(false);cin.tie(0);
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll , ll> pll;

const int maxn=1000;
int tree[maxn<<2],arr[maxn],lazy[maxn<<2];

void build(int node,int L,int R){//递归建树
	if(L==R){//当L==R时到达叶子节点，更新信息并返回
		tree[node]=arr[L];
		return;
	}
	int mid=(L+R)>>1;//区间减半，拆分为左右
	build(node<<1,L,mid);//左子树的建立
	build(node<<1|1,mid+1,R);//右子树的建立
	tree[node]=tree[node<<1]+tree[node<<1|1];//更新当前值
	return;
}

void update(int node int L,int R,int k,int v){//单点更新
	if(L==R&&L==k){//判断是否到达要更新的点
		tree[node]+=v;
		return;
	}
	int mid=(L+R)>>1;//区间折半
	if(mid>=k) update(node<<1,L,mid,k,v);//判断要修改的点是否在左区间
	else update(node<<1|1,mid+1,R,k,v);//判断要修改的点是否在右区间
	tree[node]=tree[node<<1]+tree[node<<1|1];//更新区间值
	return;
}

void Add(int node,int L,int R,int v){//区间更新
	lazy[node]+=v;//懒人标记
	tree[node]+=(R-L+1)*v;//区间值修改
	return;
}

void pushdown(int node,int L,int R){//标记下移
	if(lazy[node]==0) return;//没有标记，返回
	int mid=(L+R)>>1;
	Add(node<<1,L,mid,lazy[node]);//左区间标记和值更新
	Add(node<<1|1,mid+1,R,lazy[node]);//右区间标记和值更新
	lazy[node]=0;//此处标记归零
	return;
}

//区间更新
void update_range(int node,int L,int R,int x,int y,int v){
	if(L>=x&&R<=y){//如果当前区间位于修改区间内，则修改
		Add(node,L,R,v);//区间值修改
		return;
	}
	int mid=(L+R)>>1;
	pushdown(node,L,R);//标记下移
	if(x<=mid) update_range(node<<1,L,mid,x,y,v);//搜索左半区间
	if(y>mid) update_range(node<<1|1,mid+1,R,x,y,v);//搜索右半区间
	tree[node]=tree[node<<1]+tree[node<<1|1];//更新区间值
	return;
}

int ask(int node,int L,int R,int x,int y){
	if(L>=x&&R<=y){//如果区间位于询问区间，返回当前区间值
		return tree[node];
	}
	int mid=(L+R)>>1;
	int ans=0;
	if(x<=mid) ans+=ask(node<<1,L,mid,x,y);//判断区间是否在询问区间内，并加上区间结果
	if(y>mid) ans+=ask(node<<1|1,mid+1,R,x,y);
	return ans;
}

int query(int node,int L,int R,int x,int y){
	if(L>=x&&R<=y)//当前区间位于查询区间内
		return tree[node];//返回区间值
	int mid=(L+R)>>1;
	int ans=0;
	pushdown(node,L,R);//标记下移
	if(x<=mid) ans+=query(node<<1,L,mid,x,y);
	if(y>mid) ans+=query(node<<1|1,mid+1,R,x,y);
	return ans;
}

int main()
{
	#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	#endif
	
	return 0;
}