Wikioi 1081 線段樹練習 2：區間加、單點查詢懶標記模板

問題描述

序列長度 n，初始值給定。操作：
1 a b s：區間 [a,b] 加 s。
2 s：查詢位置 s 當前值。
多測試案例，n≤100000，操作數 q 同量級。

線段樹懶標記設計

• 節點存 `sum`（該區間值，葉子為單點值）和 `lazy`（待下傳的加值）。
• 區間加：覆蓋則直接加到 `sum` 和 `lazy`；否則下傳懶標記，遞歸子區間。
• 單點查詢：下傳懶標記至葉子，返回 `sum`。
  注意：本題僅查詢葉子，**無需 `pushUp` 維護區間聚合信息**，去掉反而略快（減少函數調用）。

關鍵代碼

#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
int sum[MAXN*4], lazy[MAXN*4];
void pushDown(int rt) {
    if (lazy[rt]) {
        lazy[rt<<1] += lazy[rt]; sum[rt<<1] += lazy[rt];
        lazy[rt<<1|1] += lazy[rt]; sum[rt<<1|1] += lazy[rt];
        lazy[rt] = 0;
    }
}
void build(int rt, int l, int r) {
    sum[rt]=lazy[rt]=0;
    if (l==r) return;
    int mid=(l+r)>>1; build(lson); build(rson);
}
void update(int rt, int l, int r, int L, int R, int v) {
    if (L<=l && r<=R) { sum[rt]+=v; lazy[rt]+=v; return; }
    int mid=(l+r)>>1; pushDown(rt);
    if (L<=mid) update(lson, L, R, v);
    if (R>mid) update(rson, L, R, v);
    // 無需 pushUp
}
int query(int rt, int l, int r, int pos) {
    if (l==r) return sum[rt];
    int mid=(l+r)>>1; pushDown(rt);
    if (pos<=mid) return query(lson, pos);
    else return query(rson, pos);
}

優化細節

• 輸入輸出用 `scanf`/`printf`，避免 iostream 慢。
• 數組大小 4*n 足夠。
• 去掉 `pushUp` 後運行時間從 3ms 降至 4ms？實測波動，但邏輯上查詢葉子不需要區間聚合值，省略合理。