HDU 1754 I Hate It

Description

中文题目

题目链接

线段树

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

int n, m;
struct node
{
    int L, R, val;
}a[N << 2 | 1] ;

void init(int num, int l, int r)
{
    a[num].L = l;
    a[num].R = r;
    a[num].val = 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].val = 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].val = max(a[num << 1].val, a[num << 1 | 1].val);
}

int query(int num, int l, int r)
{
    if(a[num].L == l && a[num].R == r)
        return a[num].val;

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

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

int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        init(1, 1, n);
        int tem, b, c;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &tem);
            update(1, i, i, tem);
        }
        getchar();
        char ch;
        for(int i = 0; i < m; ++i)
        {
            ch = getchar();
            if(ch == 'Q')
            {
                scanf("%d%d", &b, &c);
                getchar();
                cout << query(1, b, c) << '\n';
            }
            else
            {
                scanf("%d%d", &b, &c);
                getchar();
                update(1, b, b, c);
            }
        }
    }
    return 0;
}

树状数组（求最值）

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 200005;

int n, m;
int tree[N];
int init[N];

int lowbit(int x)
{
    return x & (-x);
}

void update(int x, int y)
{
    init[x] = y;
    for(int i = x; i <= n; i += lowbit(i))
        tree[i] = max(tree[i], y);
}

int get_mmax(int x, int y)
{
    int ans = init[y];
    while(y != x)
    {
        for(--y; y - lowbit(y) >= x; y -= lowbit(y))
            ans = max(ans, tree[y]);
        ans = max(ans, init[y]);
    }
    return ans;
}

int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        memset(tree, 0, sizeof(tree));
        memset(init, 0, sizeof(init));
        int tem, b, c;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &tem);
            update(i, tem);
        }
        getchar();
        char ch;
        for(int i = 0; i < m; ++i)
        {
            ch = getchar();
            if(ch == 'Q')
            {
                scanf("%d%d", &b, &c);
                getchar();
                cout << get_mmax(b, c) << '\n';
            }
            else
            {
                scanf("%d%d", &b, &c);
                getchar();
                update(b, c);
            }
        }
    }
    return 0;
}

更多关于树状数组 https://blog.csdn.net/yu121380/article/details/81431480