免费A级毛片无码专区网站-成人国产精品视频一区二区-啊 日出水了 用力乖乖在线-国产黑色丝袜在线观看下-天天操美女夜夜操美女-日韩网站在线观看中文字幕-AV高清hd片XXX国产-亚洲av中文字字幕乱码综合-搬开女人下面使劲插视频

  1. 首頁(yè) > 生活 > >

基礎(chǔ)&進(jìn)階 線段樹(shù)學(xué)習(xí)筆記（一） | P3372 【模板】線段樹(shù) 1 題解

生活百科

什么是線段樹(shù)線段樹(shù)是一棵二叉樹(shù)，每個(gè)結(jié)點(diǎn)存儲(chǔ)需維護(hù)的信息，一般用于處理區(qū)間最值、區(qū)間和等問(wèn)題 。
線段樹(shù)的用處對(duì)編號(hào)連續(xù)的一些點(diǎn)進(jìn)行修改或者統(tǒng)計(jì)操作，修改和統(tǒng)計(jì)的復(fù)雜度都是 O(log n) 。
基礎(chǔ)線段樹(shù)（+ 懶標(biāo)記）為什么不寫(xiě)沒(méi)有懶標(biāo)記的版本？因?yàn)槲姨说牟粫?huì)寫(xiě) 因?yàn)橛袘袠?biāo)記的版本更實(shí)用啦 。

  • P3372 【模板】線段樹(shù) 1
【基礎(chǔ)&進(jìn)階 線段樹(shù)學(xué)習(xí)筆記（一） | P3372 【模板】線段樹(shù) 1 題解】這是一道線段樹(shù)區(qū)間修改，區(qū)間查詢(xún)的模板題，維護(hù)的是區(qū)間和 。
1. 建樹(shù)void build(int rt, int L, int R) { l[rt] = L, r[rt] = R; if (L == R) {sum[rt] = a[L];return ; } int mid = L + R >> 1; build(rt << 1, L, mid), build(rt << 1 | 1, mid + 1, R); update(rt);}作為一棵最最普通的線段樹(shù)，它有一個(gè)性質(zhì)，對(duì)于每個(gè)結(jié)點(diǎn) x，它的左兒子的編號(hào)是 x * 2 （即代碼中的 x << 1），右兒子的編號(hào)是 x * 2 + 1 （即代碼中的 x << 1 | 1） 。代碼中的 l 和 r 數(shù)組用于記錄編號(hào)為 rt 的點(diǎn)所管轄的區(qū)間的左右端點(diǎn) 。update 是什么？它是用子節(jié)點(diǎn)的數(shù)據(jù)更新自身的數(shù)據(jù)，以保證正確性 。
  • update 的具體實(shí)現(xiàn)
void update(int rt) { sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];}它在后續(xù)的操作中也會(huì)用到 。
2. 修改void change(int rt, int L, int R, int x) { if (L <= l[rt] && r[rt] <= R) {sum[rt] += (r[rt] - l[rt] + 1) * x;lazy[rt] += x;return ; } pushdown(rt); if (L <= r[rt << 1]) change(rt << 1, L, R, x); if (l[rt << 1 | 1] <= R) change(rt << 1 | 1, L, R, x); update(rt);}其中傳入的參數(shù) L 和 R 表示需修改的區(qū)間的左右端點(diǎn)，x 表示這個(gè)區(qū)間上要加的數(shù) 。if (L <= l[rt] && r[rt] <= R) 意為當(dāng)該點(diǎn)管轄的區(qū)間被需修改的區(qū)間全覆蓋時(shí)，直接修改這個(gè)點(diǎn)上記錄的區(qū)間和，并打上懶標(biāo)記，不繼續(xù)下傳，以保證效率 。（懶標(biāo)記就是一種記錄修改操作的 tag，用于節(jié)省時(shí)間 。）pushdown 操作意為該點(diǎn)管轄的區(qū)間不完全覆蓋于需修改的區(qū)間時(shí)，下傳懶標(biāo)記 。（為什么現(xiàn)在才下傳？因?yàn)閼袠?biāo)記就是這么用的 因?yàn)楹竺娴母臅?huì)用到該點(diǎn)的子節(jié)點(diǎn)的數(shù)據(jù)，如果懶標(biāo)記不下傳，后面的修改操作就會(huì)出現(xiàn)問(wèn)題 。）下面的兩個(gè) if 是什么？if (L <= r[rt << 1]) 表示左兒子的區(qū)間中有部分（或全部）包含于詢(xún)問(wèn)區(qū)間，需統(tǒng)計(jì) 。（如果還是沒(méi)看出來(lái)就翻回去看看定義和性質(zhì)吖）那么是不是就知道 if (l[rt << 1 | 1] <= R) 是什么了？對(duì)，它表示的是右兒子的區(qū)間中有部分（或全部）包含于詢(xún)問(wèn)區(qū)間，需統(tǒng)計(jì) 。傳的參數(shù)為什么是這樣不用我說(shuō)了吧？
  • pushdown 的具體實(shí)現(xiàn)
void pushdown(int rt) { if (!lazy[rt]) return ; sum[rt << 1] += (r[rt << 1] - l[rt << 1] + 1) * lazy[rt]; sum[rt << 1 | 1] += (r[rt << 1 | 1] - l[rt << 1 | 1] + 1) * lazy[rt]; lazy[rt << 1] += lazy[rt]; lazy[rt << 1 | 1] += lazy[rt]; lazy[rt] = 0; update(rt);}在下傳懶標(biāo)記時(shí)給子節(jié)點(diǎn)的區(qū)間和加上 懶標(biāo)記的值 × 子節(jié)點(diǎn)的區(qū)間大小 。（給該子節(jié)點(diǎn)的管轄區(qū)間的所有數(shù)都加上懶標(biāo)記的值，那么該區(qū)間的區(qū)間和就會(huì)加上 懶標(biāo)記的值 × 區(qū)間長(zhǎng)度 。）同時(shí)，給子節(jié)點(diǎn)的懶標(biāo)記都加上自己的懶標(biāo)記的值 。（沒(méi)錯(cuò)我還是給你吊在那里，不給你傳到底）記得清空自己的懶標(biāo)記值并更新自己的區(qū)間和 。
3. 查詢(xún)ll query(int rt, int L, int R) { if (L <= l[rt] && r[rt] <= R) return sum[rt]; pushdown(rt); ll res = 0; if (L <= r[rt << 1]) res += query(rt << 1, L, R); if (l[rt << 1 | 1] <= R) res += query(rt << 1 | 1, L, R); return res;}

經(jīng)驗(yàn)總結(jié)擴(kuò)展閱讀