线段树
- 单点修改，单点，区间查询
- 区间修改，单点，区间查询
单点修改
普通线段树
code
#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define lll long long
const int N = 1000001;
int n,m;
int a[N];
struct T
{
int l,r,data;
} tr[N<<2];
void pushup(int rt)
{
tr[rt].data=tr[ls].data+tr[rs].data;
}
void bui(int rt,int l,int r)
{
tr[rt].l=l; tr[rt].r=r;
if(l==r)
{
tr[rt].data=a[l];
return;//注意return
}
int mid=((lll)l+r)>>1;//注意long long
bui(ls,l,mid); bui(rs,mid+1,r);
pushup(rt);
}
void mdf(int rt,int x,int v)
{
if(tr[rt].l==tr[rt].r)
{
tr[rt].data+=v;
return;
}
int mid=((lll)tr[rt].l+tr[rt].r)>>1;
if(x<=mid) mdf(ls,x,v);
else mdf(rs,x,v);
pushup(rt);
}
int que(int rt,int l,int r)
{
if(l<=tr[rt].l&&r>=tr[rt].r)
return tr[rt].data;
int mid=((lll)tr[rt].l+tr[rt].r)>>1;
int res=0;
if(l<=mid) res+=que(ls,l,r);
if(r>mid) res+=que(rs,l,r);
return res;
}
区间修改
“卤煮”存一下更新，查询时再下放。
code
#define lll long long
#define ls (rt << 1)
#define rs (rt << 1 | 1)
const int N = 100005;
int n,a[N],m;
struct T
{
int l,r,data,lz;
} tr[N<<2];
void pushup(int rt)
{
tr[rt].data=tr[ls].data+tr[rs].data;
}
void pushdown(int rt)
{
if(tr[rt].lz!=0)
{
int lz=tr[rt].lz;
tr[rt].lz=0;
tr[ls].lz+=lz;
tr[rs].lz+=lz;
tr[ls].data+=lz*(tr[ls].r-tr[ls].l+1);
tr[rs].data+=lz*(tr[rs].r-tr[rs].l+1);
}
}
void bui(int rt,int l,int r)
{
tr[rt].l=l; tr[rt].r=r;
if(l==r)
{
tr[rt].data=a[l];
return ;
}
int mid=((lll)l+r)>>1;
bui(ls,l,mid); bui(rs,mid+1,r);
pushup(rt);
}
void mdf(int rt,int l,int r,int v)
{
if(l<=tr[rt].l&&r>=tr[rt].r)
{
tr[rt].lz+=v;
tr[rt].data+=v*(tr[rt].r-tr[rt].l+1);
return;
}
int mid=((lll)tr[rt].l+tr[rt].r)>>1;
if(l<=mid) mdf(ls,l,r,v);
if(r>mid) mdf(rs,l,r,v);
pushup(rt);
}
int que(int rt,int l,int r)
{
if(l<=tr[rt].l&&r>=tr[rt].r)
return tr[rt].data;
pushdown(rt);
int mid=((lll)tr[rt].l+tr[rt].r)>>1;
int res=0;
if(l<=mid) res+=que(ls,l,r);
if(r>mid) res+=que(rs,l,r);
return res;
}
线段树就是打心态。
标签：rt,return,int,res,线段,tr,mid,板子 From： https://www.cnblogs.com/ppllxx/p/18021610