线段树

首先是建树

我们先构建整棵树的框架

struct node
{
    int l,r;
    string data;
}g[N*4];
//不一定非要构建结构体，看题目需求，如果不涉及左右范围的话就可以直接构造数组

//n表示的是树上每个结点的数值，比如说第一个结点为1，那莫第一个结点的左子树为2，右子树为3
//l(是字母l,不是数字1)和r  表示的是该结点所包含的范围  比如说结点1所包含的范围是1~8，表示结点1左子树所能到达的最左端是1，右子树所能到达的最右端是8 

void build(int u , int l , int r)
{
    g[u].l = l , g[u].r = r;//记录当前结点所包含的范围
    if(l == r) return;//如果l=r，表示该结点时叶子节点，因为他的范围只有它本身
    int mid = (l + r) >> 1;//这里注意mid应该是包含在左子树上的
    build(2 * u , l , mid);//递归到左子树上
    build(2 * u + 1 , mid + 1 , r);//递归到右子树上
}

因为我们要清楚将结点赋值与对结点的值进行修改是一样的操作，都是有改变的性质，所以我们统一用一个函数来表示

//u  还是表示的是树上每个结点的数值
//old  表示的是你要对第几个结点进行修改
//neu  表示你要对old这个结点修改为neu
void re(int u , int old , int neu)
{
    if(g[u].l == old && g[u].r == old) g[u].data = neu;//如果当前结点的左范围和右范围都等于old,表示当前这个结点是叶子结点，并且该叶子节点是old结点，那莫我们就把当前的值修改为neu
    else{
        int mid = (g[u].l + g[u].r) >> 1;//计算当前结点范围的中间值
　　　　//刚才我们说过，mid是在左子树内的
        if(old <= mid) re(u * 2 , old , neu);//如果old小于等于mid，说明我们要求的结点在当前节点的左子树上；反之，在右子树上
        else re(u * 2 + 1 , old , neu);
        g[u].data = max(g[2 * u].data , g[2 * u + 1].data);//通过左右子树的值来求出当前非叶子结点的值
    }
}

查询过程

int find(int u , int l , int r)//要注意你需要返回的值
{
    if (g[u].l >= l && g[u].r <= r) return g[u].data;   // 树中节点，已经被完全包含在[l, r]中了
    
    int mid = (g[u].l + g[u].r) >> 1;//计算当前结点范围的中间值

　　　　//刚才我们说过，mid是在左子树内的

　　　　int v=0; 
　　　　//下面这两步是死步骤，唯一不同的是看你需要求的是最大最小值，还是和
　　 if (l <= mid) v = find(u << 1, l, r);
    if (r > mid) v = max(v, find(u << 1 | 1, l, r));
    
    return v;
}

推荐牛客上的两个线段树的题

代码查看 (nowcoder.com)

代码查看 (nowcoder.com)

//这是第一个链接的完整代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+9;
string s[N];
struct node
{
    int l,r;
    string data;
}g[N*4];
int n,m;
void build(int u , int l , int r)
{
    g[u].l = l , g[u].r = r;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(2 * u , l , mid);
    build(2 * u + 1 , mid + 1 , r);
}
string find(int u , int l , int r)
{
    if (g[u].l >= l && g[u].r <= r) return g[u].data;   // 树中节点，已经被完全包含在[l, r]中了
    
    int mid = (g[u].l + g[u].r) >> 1;
    string v = "";
    if (l <= mid) v = find(u << 1, l, r);
    if (r > mid) v = max(v, find(u << 1 | 1, l, r));
    
    return v;
}
void re(int u , int old , string neu)
{
    if(g[u].l == old && g[u].r == old) g[u].data = neu;
    else{
        int mid = (g[u].l + g[u].r) >> 1;
        if(old <= mid) re(u * 2 , old , neu);
        else re(u * 2 + 1 , old , neu);
        g[u].data = max(g[2 * u].data , g[2 * u + 1].data);
    }
}
void solve()
{
    cin>>n>>m;
    build(1,1,N);
    for(int i=1;i<=n;i++)
    {
        string x;
        cin>>x;
        re(1,i,x);
    }
    
    for(int i=1;i<=m;i++)
    {
        char c;
        cin>>c;
        if(c=='U')
        {
            int idx; string x;
            cin >> idx >> x;
            re(1 , idx , x);
            
        }
        else
        {
            int l , r;
            cin >> l >> r;
            string t = find(1 , l , r);
            if(t.size() <= 0)
                t += "null";
            cout << t << endl;
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
}