树状数组
——高效求前缀和
（直接放板子了。。）
下标
点击查看代码
int lowbit(int x){
return x&(-x);
}
单点修改
点击查看代码
void add(int i,int k){
while(i<=n){
c[i]^=k;
i+=lowbit(i);
}
}
求和
点击查看代码
int getsum(int l){
int res1=0;
while(l>0){
res1^=c[l];
l-=lowbit(l);
}
return res1;
}
线段树
比树状数组牛B的东西（是个二叉树）
记得预处理。。。
点击查看代码
int lid(int id){
return id<<1;
}
int rid(int id){
return id<<1|1;
}
建树
点击查看代码
void build(int id,int l,int r)
{
m[id].lid=l;
m[id].rid=r;
if(l==r)
{
m[id].sum=a[l];
return;
}
int mid=(l+r)>>1;
build(lid(id),l,mid);
build(rid(id),mid+1,r);
m[id].sum=m[lid(id)].sum+m[rid(id)].sum;
}
下放标记
点击查看代码
void pushdown(int id)
{
if(m[id].lazy&&m[id].lid!=m[id].rid)
{
m[lid(id)].lazy+=m[id].lazy;
m[rid(id)].lazy+=m[id].lazy;
m[lid(id)].sum+=m[id].lazy*(m[lid(id)].rid-m[lid(id)].lid+1);
m[rid(id)].sum+=m[id].lazy*(m[rid(id)].rid-m[rid(id)].lid+1);
m[id].lazy=0;
}
}
单点修改
点击查看代码
void modify(int id,int x,int val)
{
if(m[id].lid==m[id].rid)
{
m[id].sum+=val;
return;
}
int mid=(m[id].lid+m[id].rid)>>1;
modify(x<=mid?lid(id):rid(id),x,val);
m[id].sum=m[lid(id)].sum+m[rid(id)].sum;
}
区间修改
点击查看代码
void add(int id,int l,int r,int s,int tt,int val)
{
if(s>r||tt<l) return;
if(s<=l&&tt>=r)
{
m[id].sum+=val*(r-l+1);
m[id].lazy+=val;
return;
}
int mid=(l+r)>>1;
//pushdown(id);
add(lid(id),l,mid,s,tt,val);
add(rid(id),mid+1,r,s,tt,val);
m[id].sum=m[lid(id)].sum+m[rid(id)].sum;
}
区间查询
点击查看代码
int find(int id,int l,int r,int s,int tt)
{
if(s>r||tt<l) return 0;
if(s<=l&&tt>=r) return m[id].sum;
int mid=(l+r)>>1;
//pushdown(id);
return find(lid(id),l,mid,s,tt)+find(rid(id),mid+1,r,s,tt);
}
单调队列
最大值
点击查看代码
void getmax()
{
int i,head=1,tail=0;
for(i=1;i<m;i++)
{
while(head<=tail&&v[tail].x<=a[i]) tail--;\
v[++tail].x=a[i],v[tail].y=i;
}
for(;i<=n;i++)
{
while(head<=tail&&v[tail].x<=a[i]) tail--;
v[++tail].x=a[i],v[tail].y=i;
while(v[head].y<i-m+1) head++;
mx[i-m+1]=v[head].x;
}
}
最小值
点击查看代码
void getmin()
{
int i,head=1,tail=0;
for(i=1;i<m;i++)
{
while(head<=tail&&v[tail].x>=a[i]) tail--;
v[++tail].x=a[i],v[tail].y=i;
}
for(;i<=n;i++)
{
while(head<=tail&&v[tail].x>=a[i])tail--;
v[++tail].x=a[i],v[tail].y=i;
while(v[head].y<i+1-m) head++;
mn[i-m+1]=v[head].x;
}
}