题解：树套树-简单版

一、题目分析

本题要求实现一种数据结构来维护一个长度为n的序列，需要支持两种操作：一是将指定位置pos的数修改为x；二是查询整数x在区间[l, r]内的前驱（即小于x且最大的数）。

二、解题思路

本题采用线段树套multiset的方法来实现。线段树用于处理区间相关的操作，每个线段树节点内部使用multiset来存储对应区间内的数值，利用multiset的有序性和查找功能来快速实现修改和查询操作。

（一）数据结构定义

struct Tree
{
    int l, r;
    multiset<int> s;
}tr[M];

定义结构体Tree表示线段树的节点，包含区间的左右端点l和r，以及一个multiset容器s，用于存储该区间内的数值。

（二）线段树相关函数

1. 建树函数build：

void build(int u, int l, int r)
{
    tr[u] = {l, r};
    tr[u].s.insert(-INF), tr[u].s.insert(INF);
    for (int i = l; i <= r; i ++ ) tr[u].s.insert(w[i]);
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

• 初始化当前线段树节点的区间[l, r]。
• 向multiset中插入两个哨兵值-INF和INF，方便后续查找操作。
• 将当前区间内的原始序列数值插入到multiset中。

• 如果不是叶子节点，则递归构建左右子树。

• 修改函数change：

void change(int u, int p, int x)
{
    tr[u].s.erase(tr[u].s.find(w[p]));
    tr[u].s.insert(x);
    if (tr[u].l == tr[u].r) return;
    int mid = tr[u].l + tr[u].r >> 1;
    if (p <= mid) change(u << 1, p, x);
    else change(u << 1 | 1, p, x);
}

• 在当前节点的multiset中删除原来位置p的数值w[p]，并插入新的数值x。

• 如果不是叶子节点，根据位置p与区间中点mid的关系，递归到相应的子树继续修改。

• 查询函数query：

int query(int u, int a, int b, int x)
{
    if (tr[u].l >= a && tr[u].r <= b)
    {
        auto it = tr[u].s.lower_bound(x);
        --it;
        return *it;
    }
    int mid = tr[u].l + tr[u].r >> 1, res = -INF;
    if (a <= mid) res = max(res, query(u << 1, a, b, x));
    if (b > mid) res = max(res, query(u << 1 | 1, a, b, x));
    return res;
}

• 如果当前节点的区间完全包含在查询区间[a, b]内，在该节点的multiset中查找x的下界it，将其减1得到前驱，返回前驱值。
• 如果当前节点区间与查询区间有部分重叠，递归查询左右子树，并取两者的最大值作为结果返回。

（三）主函数main

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    build (1, 1, n);

    while (m -- )
    {
        int op, a, b, x;
        scanf("%d", &op);
        if (op == 1)
        {
            scanf("%d%d", &a, &x);
            change(1, a, x);
            w[a] = x;
        }
        else
        {
            scanf("%d%d%d", &a, &b, &x);
            printf("%d\n", query(1, a, b, x));
        }
    }
    return 0;
}

1. 读取数列长度n和操作次数m，以及初始的数列数值。
2. 调用build函数构建线段树。
3. 循环处理每个操作：
   • 若操作类型op为1，读取位置a和新数值x，调用change函数进行修改，并更新原数列w[a]的值。
   • 若操作类型op为2，读取查询区间[a, b]和查询值x，调用query函数查询前驱并输出结果。

四、时间复杂度和空间复杂度

（一）时间复杂度

• 建树操作：每个节点插入元素的时间复杂度为(O(n\log n))，其中n是序列长度，因为插入到multiset的时间复杂度为(O(\log n))，总共插入n次。
• 修改操作：每次修改需要在multiset中删除和插入元素，时间复杂度为(O(\log n))，同时可能需要递归到子树，最多递归(O(\log n))层，所以每次修改操作的时间复杂度为(O(\log^2 n))。
• 查询操作：每次查询在每个节点的multiset中查找元素时间复杂度为(O(\log n))，最多访问(O(\log n))个节点，所以每次查询操作的时间复杂度为(O(\log^2 n))。
• 总的时间复杂度为(O(m\log^2 n))，其中m是操作次数。

（二）空间复杂度

线段树最多有(4n)个节点，每个节点的multiset存储区间内元素，最坏情况下存储(n)个元素，所以空间复杂度为(O(n\log n))。