POJ 3264 Balamced Lineup

Description

给出序列A，包含n个元素，给出q个询问，输出每个询问对应区间里最大值与最小值的差

关于RMQ问题的ST算法

https://blog.csdn.net/qq_31759205/article/details/75008659

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50005;

int n, q;
int a[N];
int big[N][20];
int sma[N][20];

void ST()
{
    for(int i = 1; i <= n; ++i)
        big[i][0] = sma[i][0] = a[i];
    for(int j = 1; (1 << j) <= n; ++j)
        for(int i = 1; i + (1 << j) - 1 <= n; ++i)
        {
            big[i][j] = max(big[i][j - 1], big[i + (1 << (j - 1))][j - 1]);
            sma[i][j] = min(sma[i][j - 1], sma[i + (1 << (j - 1))][j - 1]);
        }
}

//int rmq(int l, int r)
void RMQ(int l, int r, int & mmax, int & mmin)
{
    int k = 0;
    while( (1 << (k + 1)) <= r - l + 1 )
        ++k;
    mmax = max(big[l][k], big[r - (1 << k) + 1][k]);
    mmin = min(sma[l][k], sma[r - (1 << k) + 1][k]);
//    return max(big[l][k], big[r - (1 << k) + 1][k]) - min(sma[l][k], sma[r - (1 << k) + 1][k]);
}

int main()
{
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    ST();
    int l, r, mmax, mmin;
    while(q--)
    {
        scanf("%d%d", &l, &r);
        RMQ(l, r, mmax, mmin);
        cout << mmax - mmin << '\n';
//        cout << rmq(l, r) << '\n';
    }
    return 0;
}

Code of Segment Tree

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50005;
const int INF = 0x3f3f3f3f;

int n, q, big, small;
struct node
{
    int L, R, mmax, mmin;
} a[N << 2 | 1] ;

void init(int num, int l, int r)
{
    a[num].L = l;
    a[num].R = r;
    a[num].mmax = 0;
    a[num].mmin = 0;

    if(l == r)///初始化到叶子结点返回
        return ;

    int mid = (l + r) >> 1;
    init(num << 1, l, mid);
    init(num << 1 | 1, mid + 1, r);
}

void update(int num, int l, int r, int tot)
{
    if(a[num].L == l && a[num].R == r)
    {
        a[num].mmax = tot;
        a[num].mmin = tot;
        return ;
    }

    if(a[num].L == a[num].R)///搜索到叶子节点返回
        return ;

    int mid = (a[num].L + a[num].R) >> 1;
    if(mid >= r)
        update(num << 1, l, r, tot);
    else if(mid < l)
        update(num << 1 | 1, l, r, tot);
    else
    {
        update(num << 1, l, r, tot);
        update(num << 1 | 1, l, r, tot);
    }

    a[num].mmax = max(a[num << 1].mmax, a[num << 1 | 1].mmax);
    a[num].mmin = min(a[num << 1].mmin, a[num << 1 | 1].mmin);
}

void query(int num, int l, int r)
{
    if(a[num].L == l && a[num].R == r)
    {
        big = max(big, a[num].mmax);
        small = min(small, a[num].mmin);
        return ;
    }

    if(a[num].L == a[num].R)
        return ;

    int mid = (a[num].L + a[num].R) >> 1;
    if(mid >= r)
        query(num << 1, l, r);
    else if(mid < l)
        query(num << 1 | 1, l, r);
    else///区间范围分清楚
        query(num << 1, l, mid), query(num << 1 | 1, mid + 1, r);
}

int main()
{
    scanf("%d%d", &n, &q);
    int tem, left, right;
    init(1, 1, n);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d", &tem);
        update(1, i, i, tem);
    }
    for(int i = 1; i <= q; ++i)
    {
        big = -1, small = INF;
        scanf("%d %d", &left, &right);
        query(1, left, right);
        cout << big - small << '\n';
    }
    return 0;
}