RMQ问题：区间最大值或者最小值问题，类似的还要区间和问题
操作：
（1）求最值 ：区间内
（2）修改元素 ：点修改
线段树：用于区间处理的数据结构，用二叉树构造
复杂度：O(nlogn):二叉折半查找
查找点或者区间的时候：顺着往下查找
修改元素：直接修改叶子节点，然后自底向上更新
！！！存储空间：4n
更新和查询：更新经过的每个节点，就把这个节点剩下的数量（长度）减1
复杂度：线段是把n个数按照二叉树进行分组，每次更新有关节点的时候，这个节点下面的所有子节点都隐含被更新了，从而减少了操作次数
例题：
还是last cows
第一种做法：用结构体实现线段树
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
typedef long long LL;
typedef unsigned long long ull;
//线段树做法
/*
从后往前遍历输入的序列，遇到的每个值a表示此牛在剩余牛中排在第a+1个，删除此编号，循环此过程，最终得到的序列即为牛在此队列中的编号序列。
借助线段树查找未删除的数中排在第a+1个位置（编号排序位置）的牛的位置（读取顺序）
*/
struct node{
int l,r,len;
}cow[100000];
int s[100000],ans[100000];
void build(int v,int l,int r){
cow[v].l=l;
cow[v].r=r;
cow[v].len=r-l+1;
if(l==r) return;
int mid=(l+r)/2;
build(v*2,l,mid);
build(v*2+1,mid+1,r);
}
int que(int v,int k){
--cow[v].len;
if(cow[v].l==cow[v].r) return cow[v].r;
//找到叶子节点, 注意此处不可用cow[v].len == 0代替，否则单支情况将直接返回，导致未达到最末端
else if(cow[v*2].len>=k){
return que(v*2,k);
}
else return que(v*2+1,k-cow[v*2].len);////！！！！
}
int main(){
int n;
while(~scanf("%d",&n)){
for(int i=2;i<=n;i++) scanf("%d",&s[i]);
s[1]=0;
build(1,1,n);
for(int i=n;i>=1;i--){
ans[i]=que(1,s[i]+1);
}
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
}
return 0;
}
第二种做法
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=11010;
const int INF=0x3fffffff;
typedef long long LL;
typedef unsigned long long ull;
//数组实现线段树
int n;
int pre[maxn],tree[maxn*4]={0},ans[maxn]={0};
void build(int n,int last_left){
for(int i=last_left;i<last_left+n;i++) tree[i]=1; //最后一行赋值
//从二叉树的最后一行倒推到根节点，根节点的值是牛的总数
while(last_left!=1){
for(int i=last_left/2;i<last_left;i++) tree[i]=tree[i*2]+tree[i*2+1];
last_left/=2;
}
}
int que(int u,int num,int last_left){ //查询+维护，求出当前区间中坐起第num个元素
tree[u]--;
if(tree[u]==0&&u>=last_left) return u;
if(tree[u<<1]<num) //左子区间数量不够，查到右子区间
return que((u<<1)+1,num-tree[u<<1],last_left);
if(tree[u<<1]>=num) //左子区间数量够了
return que(u<<1,num,last_left);
}
int main(){
int las;
scanf("%d",&n);
pre[1]=0;
for(int i=2;i<=n;i++) scanf("%d",&pre[i]);
las=1<<(int(log(n)/log(2))+1);
//cout<<las<<endl;
build(n,las); //从后往前退出每次最后一个数字
for(int i=n;i>=1;i--) ans[i]=que(1,pre[i]+1,las)-las+1;
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}
当数据太大：也可以考虑离散化，把原有的大二叉树压缩为小二叉树，但是压缩前后子区间的关系不变
区间修改
操作：（1）加 （2）查询和
lazy_tag方法：当修改一个整块区间时，只对这个线段区间进行整体上的修改，其内部每个元素内容先不修改，只有当这部分线段的一致性被破坏时才把变化之传给子区间（查询时也一样）
tag[]数组：记录节点i是否用到lazy原理，其值是op a b c中的c，如果做了多次lazy,那么add[]可以累加，如果在某次操作中被深入， 破坏了lazy,那么add[]归0
POJ 3468 A Simple Problem with Integers
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
//有错
const int maxn=1e5+5;
const int INF=0x3fffffff;
typedef long long LL;
LL summ[maxn<<2],add[maxn<<2]; //4倍空间
void pusup(int r){ //向上更新，把值给i递归到父节点 什么时候使用这个函数呢？当现在的节点发生变化，需要顺便改变父节点
summ[r]=summ[r<<1]+summ[r<<1|1];
}
void push_down(int rt,int m){ //更新r的子节点，m为长度
if(add[rt]){
add[rt<<1]+=add[rt];
add[rt<<1|1]+=add[rt];
summ[rt<<1]+=(m-(m>>1))*add[rt];
summ[rt<<1|1]+=(m>>1)*add[rt];
add[rt]=0; //取消本层的标记
}
}
void build(int l,int r,int rt){ //用满二叉树建树
add[rt]=0;
if(l==r) {
scanf("%lld",&summ[rt]); //叶子节点 赋值
return;
}
int mid=(l+r)/2;
build(l,mid-1,rt<<1);
build(mid+1,r,rt<<1|1);
pusup(rt); //这是个递归结构 向上更新区间和
}
void update(int a,int b,LL c,int l,int r,int rt){ //区间更新，
if(a<=l&&b>=r){ //lazy方法，包含在区间里面，就整体更新
summ[rt]+=(r-l+1)*c;
add[rt]+=c;
return;
}
push_down(rt,r-l+1); //向下更新
int mid=(l+r)/2;
//这里就是在处理有分叉的情况
if(a<=mid) update(a,b,c,l,mid-1,rt<<1); //分成两半，继续深入
if(b>mid) update(a,b,c,mid+1,r,rt<<1|1);
pusup(rt); //向上更新
}
LL que(int a,int b,int l,int r,int rt){ //区间求和
if(a<=l&&b>=r) return summ[rt]; //满足lazy直接返回
push_down(rt,r-l+1); //向下更新
int mid=(l+r)/2;
LL ans=0;
if(a<=mid) ans+=que(a,b,l,mid-1,rt<<1);
if(b>mid) ans+=que(a,b,mid+1,r,rt<<1|1);
return ans;
}
int main(){
int n,m;
scanf("%d %d",&n,&m);
build(1,n,1); //先建树
while(m--){
string str;
int a,b;
LL c;
cin>>str;
if(str[0]==‘C‘){
scanf("%d %d %lld",&a,&b,&c);
update(a,b,c,1,n,1);
}
else{
scanf("%d %d",&a,&b);
printf("%lld\n",que(a,b,1,n,1));
}
}
return 0;
}
原文：https://www.cnblogs.com/shirlybaby/p/12772698.html