线段树真是一个很重要很重要的数据结构！！！
一、概念
线段树是一棵二叉树，每个节点维护序列的一段区间
二、复杂度
o（nlogn）
开数组一般要开四倍空间
三、相关量
儿子：除了叶子节点，每个节点都有左儿子和右儿子
左儿子：左儿子的节点编号是父节点的两倍2 * ro，对应父节点左一半区间【l，mid】
右儿子：右儿子的节点编号是父节点的二倍加一2 * ro + 1，对应父节点右一半区间【mid + 1，r】
四、一些操作
1、建树o（n）
我比较喜欢用结构体存每个节点的信息
struct node
{
LL l,r,w,laz;
}tr[400005]
l存区间左端点，r存区间右端点，w存节点权值（区间和），laz是加法乘法标记，数组下标是节点编号
然后就是递归建图
void build(LL ro,LL ll,LL rr) { tree[ro].l = ll; tree[ro].r = rr; if(ll == rr) { scanf("%lld",&tree[ro].w); tree[ro].c = 1; tree[ro].f = 0; return; } LL mid = (ll + rr) / 2; build(ro * 2,ll,mid); build(ro * 2 + 1,mid + 1,rr); tree[ro].w = tree[ro * 2].w + tree[ro * 2 + 1].w; tree[ro].w %= mod; tree[ro].c = 1; tree[ro].f = 0; }
2、单点修改&区间修改o（logn）
记得每次修改前都先下穿一下lazy标记，先乘再加
void down(LL ro) { tree[ro * 2].c *= tree[ro].c; tree[ro * 2 + 1].c *= tree[ro].c; tree[ro * 2].c %= mod; tree[ro * 2 + 1].c %= mod; tree[ro * 2].f = tree[ro * 2].f * tree[ro].c + tree[ro].f; tree[ro * 2 + 1].f = tree[ro * 2 + 1].f * tree[ro].c + tree[ro].f; tree[ro * 2].f %= mod; tree[ro * 2 + 1].f %= mod; tree[ro * 2].w = tree[ro * 2].w * tree[ro].c + tree[ro].f * (tree[ro * 2].r - tree[ro * 2].l + 1); tree[ro * 2 + 1].w = tree[ro * 2 + 1].w * tree[ro].c + tree[ro].f * (tree[ro * 2 + 1].r - tree[ro * 2 + 1].l + 1); tree[ro].w = tree[ro * 2].w + tree[ro * 2 + 1].w; tree[ro * 2].w %= mod; tree[ro * 2 + 1].w %= mod; tree[ro].w %= mod; tree[ro].f = 0; tree[ro].c = 1; }
void changeadd(LL ro) { if(tree[ro].l >= lll && tree[ro].r <= rrr) { tree[ro].w += (tree[ro].r - tree[ro].l + 1) * xxx; tree[ro].f += xxx; tree[ro].w %= mod; tree[ro].f %= mod; return ; } down(ro); LL mid = (tree[ro].l + tree[ro].r) / 2; if(lll <= mid)changeadd(ro * 2); if(rrr > mid)changeadd(ro * 2 + 1); tree[ro].w = tree[ro * 2].w + tree[ro * 2 + 1].w; return ; } void changemul(LL ro) { if(tree[ro].l >= lll && tree[ro].r <= rrr) { tree[ro].w *= xxx; tree[ro].c *= xxx; tree[ro].f *= xxx; tree[ro].w %= mod; tree[ro].c %= mod; tree[ro].f %= mod; return ; } down(ro); LL mid = (tree[ro].l + tree[ro].r) / 2; if(lll <= mid)changemul(ro * 2); if(rrr > mid)changemul(ro * 2 + 1); tree[ro].w = tree[ro * 2].w + tree[ro * 2 + 1].w; tree[ro].w %= mod; return ; }
3、单点查询&区间查询o（logn）
每次查询前也不要忘了下传lazy标记
void ask(LL ro) { if(tree[ro].l >= lll && tree[ro].r <= rrr) { ans += tree[ro].w; ans %= mod; return ; } down(ro); int mid = (tree[ro].l + tree[ro].r) / 2; if(lll <= mid)ask(ro * 2); if(rrr > mid)ask(ro * 2 + 1); }
五、题
没事应该常回来看看刷刷