树状数组单点修改&区间最值

这是树状数组最后一个基础功能,更完树状数组在基础知识上就完结撒花了.

• 来看个很简单的模板题.https://www.luogu.com.cn/problem/P2880 贴一下这个题的代码,然后讲解.

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int h[N];
int n,q;
int hmin[N],hmax[N];
int lowbit(int x)   {  return x&(-x); }
void add(int pos,int val)//在点pos更新值为val.
{
    h[pos]=val;//这句没必要.
    while(pos<=n)
    {
        hmax[pos]=max(val,hmax[pos]);
        hmin[pos]=min(val,hmin[pos]);
        int cnt=lowbit(pos);
        for(int i=1;i<cnt;i<<=1)
        {
            hmin[pos]=min(hmin[pos-i],hmin[pos]);
            hmax[pos]=max(hmax[pos-i],hmax[pos]);
        }
        pos+=lowbit(pos);
    }
}

int mx(int l,int r)//查询区间l,r的max.
{
    int res=0;
    while(r>=l)
    {
        res=max(h[r],res),r--;
        for(;r-lowbit(r)>=l;r-=lowbit(r))
        {
            res=max(hmax[r],res);
        }
    }
    return res;
}

int mi(int l,int r)//查询区间l,r的min.
{
    int res=2e9;
    while(r>=l)
    {
        res=min(h[r],res),r--;
        for(;r-lowbit(r)>=l;r-=lowbit(r))
        {
            res=min(hmin[r],res);
        }
    }
    return res;
}

int main()
{
    scanf("%d%d",&n,&q);
    memset(hmin,0x3f,sizeof hmin);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&h[i]);
        add(i,h[i]);
    }
    while(q--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",mx(l,r)-mi(l,r));
    }
    return 0;
}

不急,我们从add函数讲起.因为这个区间将修改一个值对吧.所以呢,我们假如要更新一个区间就是[r-lowbit(r)+1,r]对吧,我们就可以直接用以前的区间更新这个区间的最大值,具体就是10000=1+10+100+1000+1.这样add函数就讲完了.那么query呢?直接利用树状数组的维护加点小小的操作就好了.当然这题是没改变原有的数组,所以我们还是加一句比较好.

貌似这个代码有点小小的问题...幸好今晚试水了...没问题的代码如下：https://paste.ubuntu.com/p/7Hmr5H8MKx/