線段樹合併及其相關問題

一、線段樹合併題目

線段樹是一種常用的數據結構，在解決區間查詢、修改問題時非常方便。但是，在實際的問題中，我們常常需要對兩個不同的線段樹進行合併，以便更好地完成某些操作。典型的線段樹合併題目包括P3834 【模板】動態開點線段樹和P3835 【模板】動態開點線段樹 2。在這些問題中，我們需要實現線段樹的合併、修改、查詢等操作，並保證時間和空間效率。下面我們將詳細介紹線段樹的合併策略及其相關問題。

二、線段樹合併max卷積

max卷積是一種常見的操作，它可以將兩個長度為n的序列A和B卷積成長度為n的序列C，其中C[i] = max(A[j] + B[i-j+1])。這個操作可以通過線段樹實現。我們首先將A和B分別建立線段樹，然後按照遞歸合併的方法來合併這兩個線段樹。在合併過程中，我們需要記錄下每個區間內A和B的最大值，以便計算C。具體的代碼示例如下：

const int N = 1e5 + 5;

struct SegmentTree {
    int l, r;
    int mx[N << 2], val[N << 2];

    inline void pushup(int o) {
        mx[o] = max(mx[o << 1], mx[o <l = l, this->r = r;
        if (l == r) {
            val[o] = mx[o] = read();
            return;
        }
        int mid = (l + r) >> 1;
        build(o << 1, l, mid);
        build(o <> 1;
        if (p <= mid)
            update(o << 1, p, v);
        else
            update(o << 1 | 1, p, v);
        pushup(o);
    }

    int query(int o, int ql, int qr) {
        if (ql = r)
            return mx[o];
        int mid = (l + r) >> 1;
        int ret = 0;
        if (ql <= mid)
            ret = max(ret, query(o < mid)
            ret = max(ret, query(o << 1 | 1, ql, qr));
        return ret;
    }
};

int n, m, a[N], b[N];
SegmentTree sa, sb;

int main() {
    n = read(), m = read();
    sa.build(1, 1, n);
    sb.build(1, 1, n);
    for (int i = 1; i = 0; --j) {
                int tmp = ans | (1 <= a[x] + b[y])
                    ans = tmp;
            }
            print(ans);
        }
    }
    return 0;
}

三、線段樹合併 劉汝佳

劉汝佳在線段樹合併問題中提出了一個有趣的做法，即將兩個線段樹的節點按照層次進行配對，然後用一個vector來記錄配對結果。在遞歸合併兩個線段樹的過程中，我們先判斷兩個節點是否在同一層，若是則將它們配對，否則將兩棵子樹進一步遞歸合併。這種方法在時間複雜度和空間複雜度上都有優化。具體的代碼示例如下：

const int N = 100005;

struct SegmentTree {
    int l, r;
    int sum;
    vector vec;

    inline void init() {
        vec.push_back(0);
        vec.push_back(0);
    }

    inline int size() {
        return vec.size() - 2;
    }

    inline void update(int x) {
        vec.push_back(x);
    }

    inline int top() {
        return vec.back();
    }
};

SegmentTree T[N <> 1;
        T[o].l = build(l, mid);
        T[o].r = build(mid + 1, r);
        T[o].sum = T[T[o].l].sum + T[T[o].r].sum;
        int ln = T[T[o].l].size() + 1, rn = T[T[o].r].size() + 1;
        for (int i = 1, j = 1; i <= ln || j <= rn;) {
            if (i  rn || T[T[o].l].vec[i] > T[T[o].r].vec[j]))
                T[o].update(T[T[o].l].vec[i++] + 1);
            else
                T[o].update(T[T[o].r].vec[j++] + 1);
        }
        L[o] = T[T[o].l].size() + 1;
        R[o] = T[o].size() - T[T[o].r].size();
        root[L[o]] = T[o].l, root[R[o]] = T[o].r;
    }
    return o;
}

void modify(int x, int pre, int l, int r, int p, int v) {
    int o = ++cnt;
    T[o].init();
    T[o].sum = T[pre].sum + v;
    T[o].vec = T[pre].vec;
    if (l == r) {
        T[o].update(T[pre].top() + v + 1);
    } else {
        int mid = (l + r) >> 1;
        if (p <= mid)
            T[o].l = ++cnt, modify(x, T[pre].l, l, mid, p, v), T[o].r = T[pre].r;
        else
            T[o].r = ++cnt, modify(x, T[pre].r, mid + 1, r, p, v), T[o].l = T[pre].l;
        T[o].sum = T[T[o].l].sum + T[T[o].r].sum;
        int ln = T[T[o].l].size() + 1, rn = T[T[o].r].size() + 1;
        for (int i = 1, j = 1; i <= ln || j <= rn;) {
            if (i  rn || T[T[o].l].vec[i] > T[T[o].r].vec[j]))
                T[o].update(T[T[o].l].vec[i++] + 1);
            else
                T[o].update(T[T[o].r].vec[j++] + 1);
        }
        L[o] = T[T[o].l].size() + 1;
        R[o] = T[o].size() - T[T[o].r].size();
        root[L[o]] = T[o].l, root[R[o]] = T[o].r;
    }
}

int query(int l, int r, int k) {
    if (l == r)
        return l;
    int sum = 0;
    for (int i = 1; i <= cnt; ++i) {
        if (k = L[i] && k = L[i] + 1)
            sum -= T[T[root[L[i] - 1]].r].sum;
        if (sum >= l)
            return query(l, (l + r) >> 1, i);
    }
    return 0;
}

int main() {
    int n = read(), m = read(), a[N], b[N];
    root[0] = build(1, n);
    for (int i = 1; i <= m; ++i) {
        int op = read(), x = read(), y = read();
        if (op == 1) {
            modify(++n, root[n - 1], 1, n, x, y);
        } else {
            int l = read(), r = read();
            int pos = query((r - l + 2) / 2, 1e9, n);
            int ans = T[root[pos]].vec[r - pos + 1] - 1;
            printf("%d\n", ans);
        }
    }
    return 0;
}

四、線段樹合併 永無鄉

永無鄉提出的線段樹合併方法則是以差分的形式進行。我們首先對區間進行差分，然後建立線段樹。在合併兩棵線段樹時，我們先將兩棵線段樹分別按照深度從大到小遍歷，建立新的線段樹，並按照從小到大的順序，將差分的結果進行合併。需要注意的是，在合併中，我們需要判斷相鄰的兩個區間是否可以合併。具體的代碼示例如下：

const int N = 4e6 + 5;
struct SegmentTree {
 int l, r;
 int s, c;
 int lc, rc;
} T[N];
int n, m, cnt;
void pushup(int o) {
 if (T[o].l == T[o].r) return;
 T[o].c = T[T[o].lc].c + T[T[o].rc].c;
 if (T[T[o].lc].s == T[T[o].lc].c)
 T[o].lc = T[T[o].lc].rc = 0;
 if (T[T[o].rc].s == T[T[o].rc].c)
 T[o].rc = T[T[o].rc].lc = 0;
}
void build(int &o, int l, int r) {
 o = ++cnt;
 T[o].l = l, T[o].r = r, T[o].c = T[o].s = 0;
 if (l == r) return;
 int mid = (l + r) >> 1;
 build(T[o].lc, l, mid);
 build(T[o].rc, mid + 1, r);
}
void modify(int o, int p, int v) {
 if (T[o].l == T[o].r) {
 T[o].s += v;
 T[o].c = T[o].s;
 return;
 }
 int mid = (T[o].l + T[o].r) >> 1;
 if (p <= mid)
 modify(T[o].lc, p, v);
 else
 modify(T[o].rc, p, v);
 pushup(o);
}
int merge(int o1, int o2) {
 if (!o1 || !o2)
 return o1 + o2;
 int o = ++cnt;
 T[o].l = T[o1].l, T[o].r = T[o1].r;
 if (T[o1].l == T[o1].r) {
 T[o].c = T[o].s = (T[o1].s || T[o2].s);
 return o;
 }
 T[o].lc = merge(T[o1].lc, T[o2].lc);
 T[o].rc = merge(T[o1].rc, T[o2].rc);
 pushup(o);
 return o;
}
int main() {
 n = read();
 build(root, 1, n);
 for (int i = 1; i <= n; ++i)
 modify(root, i, read());
 m = read();
 while (m--) {
 int op = read(), l = read(), r = read();
 if (op == 1) {
 modify(root, l, r);
 }
原創文章，作者：XELKF，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/332244.html