大二上数算实习advds1线段树

[a,(a+b)/2] [(a+b)/2+1,b]12312345678912345678912345678912345678989找点:根据定义，从根一直走到叶子logn总时间O(log

查询

建树，数据，查找、统计等工作，提供了理论依据

{a,*lch,}st[maxn*intm=voidbuild(inti,intx,int{st[i].a=st[i].b=if(x<{st[i].lch=•}}2.RMQ{if{}}if(x<{}

st[i].lch= st[i].rch= elsest[i].f {if{}}voidchange(Node*p,intk,int{if(p->a!=p-{

intmid=(p->a+p->b)/ifkmid)change(p->lch,k, if(kmid)change(p->rch,k, }elsep->f }{{}}voidquery(Node*p,intx,int{if(p->a>=x&&p->b<=y)ans=min(ans,p-{intmid=(p->a+p->b)/if(x<=mid)query(p->lch,x,if(y>mid)query(p->rch,x,}}每次修改的复杂度为O(logn)每次询问的复杂度为O(logn)问的结点不会超过4个（为什么呢O_O自己模拟一下就知道了）。总复杂度为O(mlogn)，mF(n)包括没有使用的下标为0若n=2k,若2(n+1)<=F(n)<=F(n)<= 转 5

[4,4]

7它的左儿子为[1,1]

voidbuild(intid,intl,int{tree[id].left=l;tree[id].right=r;if(l==r){}{}}

intmid=(l+r)/2; voidupdate(intid,intpos,int{if{}{}}

intmid=(tree[id].left+tree[id].right)/2;if(pos<=mid)update(id*2,pos,val);elseupdate(id*2+1,pos,val);voidquery(intid,intl,int{returntree[id].sum;//询问总和{}}

if(r<=mid)returnquery(id*2,l,r);elseif(l>mid)returnquery(id*2+1,l,r)return3. 询问当前有多少条单位线段[kk+1]被涂影响的结点，若染色[l，r]区间，则被影响的结点一共有(r-l)*2个，已经不是O(logn) 前结点以及它的都被染色过，直到下st[i].flagflag0表示当前结点没有标记，也就是既没flag==1表示当前结点以及整棵都被染色flag==-1表示当前结点以及整棵都被擦{if(p->a>=x&&p->b<={p->flag=

}{

根据标记整理当前结点信 if(p->flag!={

p->lch->flagp->rch->flagp 根据标记整理的信 p->flag=}intmid=(p->a+p->b)/if(x<=mid)change(p->lch,x,y,if(y>mid)change(p->rch,x,y,

根据的信息更新当前结 }} 两项操作的复杂度还是O(logn) 4.例 POJ2528Mayor's给定一些海报，可能互相，告诉你每POJ2528Mayor's（题意为整个墙都会被盖到POJ2528Mayor'sPOJ2528Mayor'sstruct{intboolCNode*pLeft,* [1,1][2,2][3,3][4,4] 1000120[2,2][4,4] 00 10

1 0120[2,2][4,4]00 10 建树有b ，共m次查询，因此时间复杂度为

331