大二上數(shù)算實(shí)習(xí)advds1線段樹(shù)

[a,(a+b)/2] [(a+b)/2+1,b]12312345678912345678912345678912345678989找點(diǎn):根據(jù)定義，從根一直走到葉子logn總時(shí)間O(log

查詢

建樹(shù)，數(shù)據(jù)，查找、統(tǒng)計(jì)等工作，提供了理論依據(jù)

{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,}}每次修改的復(fù)雜度為O(logn)每次詢問(wèn)的復(fù)雜度為O(logn)問(wèn)的結(jié)點(diǎn)不會(huì)超過(guò)4個(gè)（為什么呢O_O自己模擬一下就知道了）?？倧?fù)雜度為O(mlogn)，mF(n)包括沒(méi)有使用的下標(biāo)為0若n=2k,若2(n+1)<=F(n)<=F(n)<= 轉(zhuǎ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;//詢問(wèn)總和{}}

if(r<=mid)returnquery(id*2,l,r);elseif(l>mid)returnquery(id*2+1,l,r)return3. 詢問(wèn)當(dāng)前有多少條單位線段[kk+1]被涂影響的結(jié)點(diǎn)，若染色[l，r]區(qū)間，則被影響的結(jié)點(diǎn)一共有(r-l)*2個(gè)，已經(jīng)不是O(logn) 前結(jié)點(diǎn)以及它的都被染色過(guò)，直到下st[i].flagflag0表示當(dāng)前結(jié)點(diǎn)沒(méi)有標(biāo)記，也就是既沒(méi)flag==1表示當(dāng)前結(jié)點(diǎn)以及整棵都被染色flag==-1表示當(dāng)前結(jié)點(diǎn)以及整棵都被擦{if(p->a>=x&&p->b<={p->flag=

}{

根據(jù)標(biāo)記整理當(dāng)前結(jié)點(diǎn)信 if(p->flag!={

p->lch->flagp->rch->flagp 根據(jù)標(biāo)記整理的信 p->flag=}intmid=(p->a+p->b)/if(x<=mid)change(p->lch,x,y,if(y>mid)change(p->rch,x,y,

根據(jù)的信息更新當(dāng)前結(jié) }} 兩項(xiàng)操作的復(fù)雜度還是O(logn) 4.例 POJ2528Mayor's給定一些海報(bào)，可能互相，告訴你每POJ2528Mayor's（題意為整個(gè)墻都會(huì)被蓋到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 建樹(shù)有b ，共m次查詢，因此時(shí)間復(fù)雜度為

331