线段树合并及其相关问题

一、线段树合并题目

线段树是一种常用的数据结构，在解决区间查询、修改问题时非常方便。但是，在实际的问题中，我们常常需要对两个不同的线段树进行合并，以便更好地完成某些操作。典型的线段树合并题目包括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 << 1 | 1]);
    }

    void build(int o, int l, int r) {
        this->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 | 1, mid + 1, r);
        pushup(o);
    }

    void update(int o, int p, int v) {
        if (l == r) {
            val[o] = mx[o] = v;
            return;
        }
        int mid = (l + r) >> 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 <= l && qr >= r)
            return mx[o];
        int mid = (l + r) >> 1;
        int ret = 0;
        if (ql <= mid)
            ret = max(ret, query(o << 1, ql, qr));
        if (qr > 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 <= m; ++i) {
        int op = read(), x = read(), y = read();
        if (op == 1) {
            sa.update(1, x, y);
            sb.update(1, x, y);
        } else {
            int ans = 0;
            for (int j = 30; j >= 0; --j) {
                int tmp = ans | (1 << j);
                int mx1 = sa.query(1, x, x + tmp - 1);
                int mx2 = sb.query(1, n - y + 1, n - y + 1 + tmp - 1);
                if (mx1 + mx2 >= 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 << 2];
int root[N], L[N], R[N], cnt;

int build(int l, int r) {
    int o = ++cnt;
    if (l == r) {
        T[o].sum = read();
        T[o].init();
    } else {
        int mid = (l + r) >> 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 <= ln && (j > 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 <= ln && (j > 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 <= R[i] - 1)
            sum += T[T[root[R[i] - 1]].r].sum;
        if (k >= L[i] && k <= R[i])
            sum += T[T[root[k - 1]].r].sum;
        if (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);
        }