觉得y总的板子不够优美,自己(尝试)写了一个
//线段树左右儿子定义
#define lson o<<1
#define rson o<<1|1
#define mid (l+r>>1)
int a[100010];//初始数据
//线段树的定义(结构体)
struct segtree{
int laz;//懒标记,根据题目不同可能需要多个懒标记
// TODO:题目要求维护的区间信息
}dat[100010<<2];//开四倍的空间
//上推
void update(int o)
{
//TODO:利用左右儿子信息维护(更新)当前节点信息
}
//建树
void build(int o, int l, int r)
{//o为当前节点,l和r分别为为o对应的区间边界
if(l == r)
{//当前为叶子节点
//因为是叶子节点,所以用原始数据更新需要维护的数据
dat[o]. = a[l];
return;
}
//递归左右子树
build(lson, l, mid);
build(rson, mid+1, r);
//因为只更新了叶子节点,所以需要上推更新父节点
update(o);
}
//将懒标记下传
void pushdown(int o, int l, int r)
{
if(dat[o].laz)
{
//TODO:利用懒标记更新左右儿子的区间信息
//修改左右儿子的懒标记
dat[lson].laz += dat[o].laz;
dat[rson].laz += dat[o].laz;
}
//将当前节点的懒标记清零
dat[o].laz = 0;
}
//区间修改
void modify(int o, int l, int r, int ql, int qr, int v)
{//o为当前节点,l和r为o所对应的区间,ql和qr为需要修改的区间,v为修改的值
if(l >= ql && r <= qr)
{
//TODO:修改当前区间信息
//为当前区间打上懒标记
dat[o].laz += v;
return;
}
//因为要递归访问左右儿子,所以要将懒标记下传
pushdown(o, l, r);
if (ql <= mid)
modify(lson, l, mid, ql, qr, v);
if (qr > mid)
modify(rson, mid + 1, r, ql, qr, v);
//利用儿子节点更新父亲
update(o);
}
//查询(返回要查询的值)
int query(int o, int l, int r, int ql, int qr)
{
if (l >= ql && r <= qr)
return ; //返回当前的区间信息
//将懒标记下传
pushdown(o, l, r);
int res = 0;
if (ql <= mid)
res += query(lson, l, mid, ql, qr);
if (qr > mid)
res += query(rson, mid + 1, r, ql, qr);
return res;
}