build 需要 的時間,那麼一次詢問要多少時間呢?這樣的作法中,我們只會走到上面那張圖裡紅色與藍色的節點,藍色的節點就是我們遇到 l <= L && R <= r 然後直接回傳記錄的最大值的時候,也就是遞迴的終止節點。仔細觀察一下,其實紅色與藍色的節點們都一定是「對應到 和 的節點的祖先,以及它們祖先的兄弟」,而因為樹深度是 ,因此一次詢問的時間複雜度是 。
// 區間 [l,r] 加上 v voidmodify(int l, int r, int v, int L, int R, int id){ if(l <= L && R <= r){ addtag(v, id); return; } push(id); if(r <= M) modify(l, r, v, L, M, lc); elseif(l > M) modify(l, r, v, M + 1, R, rc); else{ modify(l, r, v, L, M, lc); modify(l, r, v, M + 1, R, rc); } seg[id].mx = max(seg[lc].mx, seg[rc].mx); }
intquery(int l, int r, int L, int R, int id){ if(l <= L && R <= r) return seg[id].mx; push(id); int M = (L + R) / 2; if(r <= M) returnquery(l, r, L, M, lc); elseif(l > M) returnquery(l, r, M + 1, R, rc); elsereturnmax(query(l, r, L, M, lc), query(l, r, M + 1, R, rc)); }
structNode{ Info info; // 線段樹上儲存的資訊 Tag tag; // 懶人標記 };
vector<Node> seg; // 存線段樹的陣列
voidpull(int id){ /* 從 id 的子節點資訊更新 id 的資訊 */ } voidaddtag(Tag tag, int id){ seg[id].info = 用 tag 更新 seg[id].info; seg[id].tag += tag; } voidpush(int id){ addtag(seg[id].tag, lc); addtag(seg[id].tag, rc); // 把 seg[id].tag 清空 }
voidbuild(int L = 1, int R = N, int id = 1){ if(L == R){ // 從原始資料算 seg[id].info return; } int M = (L + R) / 2; build(L, M, lc); build(M + 1, R, rc); pull(id); }
voidmodify(int l, int r, Tag v, int L, int R, int id){ if(l <= L && R <= r){ addtag(v, id); return; } push(id); if(r <= M) modify(l, r, v, L, M, lc); elseif(l > M) modify(l, r, v, M + 1, R, rc); else{ modify(l, r, v, L, M, lc); modify(l, r, v, M + 1, R, rc); } pull(id); }
Info query(int l, int r, int L, int R, int id){ if(l <= L && R <= r) return seg[id].info; push(id); int M = (L + R) / 2; if(r <= M) returnquery(l, r, L, M, lc); elseif(l > M) returnquery(l, r, M + 1, R, rc); elsereturnquery(l, r, L, M, lc) + query(l, r, M + 1, R, rc)); }
Tag 是表示修改資訊(懶標其實就是在把修改資訊記在結點上),例如要加上多少、要改成什麼等等。Tag 的相加是表示將兩個操作合起來,例如加上 再加上 可以合成加上 ,而 Info 相加則是把兩個節點的資訊拼起來,例如在上面的例子中是把兩個數取 max。