树状数组

2021-05-16 12:28

阅读:385

标签:algorithm   printf   lib   print   nbsp   color   数组   main   math   

树状数组的应用:

  1.单点修改,区间查询。

   2.区间修改,单点查询。

   3.区间修改,区间查询。

  实际求解问题的时候经常会用树状数组来维护一个区间,因为相比线段树来说树状数组常数比较优越而且代码实现上比较容易,空间需要也比较少。

应用模板:

  1.单点修改,区间查询。

 

#includeusing namespace  std;
#define ll long long
#define INF 0x3f3f3f3f
#define maxn 1000009
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch‘0||ch>9){if(ch==-)f=-1;ch=getchar();}
    while(ch>=0&&ch‘9){x=(x1)+(x3)+(ll)(ch-0);ch=getchar();}
    return x*f;
}
ll sum[maxn];
ll n,m,k,ans,tot;

ll lowbit(ll x)
{
    return x&(-x);
}
void add(ll x,ll y)
{
    while(xn)
    {
        sum[x]+=y;
        x+=lowbit(x);
    }
}
ll Query(ll l)
{
    ans=0;
    while(l>0)
    {
        ans+=sum[l];
        l-=lowbit(l); 
    }
    return ans;
}
int main()
{
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    n=read(),m=read();
    for(int i=1;i)
    {
        ll x=read();
        add(i,x);
    }
    for(int i=1;i)
    {
        ll opt=read(),l=read(),r=read();
        if(opt==1)
            add(l,r);
        else 
            printf("%d\n",Query(r)-Query(l-1));
    }
//    fclose(stdin);
//    fclose(stdout);
    return 0;
}

 

 

 

  2.区间修改,单点查询。

  Matrix:http://poj.org/problem?id=2155

#include
#include
#include
#include
#include
#includeusing namespace std;
#define re register int 
#define ll long long
#define INF 0x3f3f3f3f
#define maxn  1009
#define maxm
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch‘0||ch>9){if(ch==-)f=-1;ch=getchar();}
    while(ch>=0&&ch‘9){x=(x1)+(x3)+(ll)(ch-0);ch=getchar();}
    return x*f;
}
int sum[maxn][maxn];
int n,m,k,ans,tot,T; 

int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int y,int z)
{
    for(re i=x;ilowbit(i))
        for(re j=y;jlowbit(j))
            sum[i][j]+=z;
}

int Query(int x,int y)
{
    int ans=0;
    for(re i=x;i>0;i-=lowbit(i))
        for(re j=y;j>0;j-=lowbit(j))
            ans+=sum[i][j];
    return ans;
}
int main()
{
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    T=read();
    for(re t=1;t)
    {
        memset(sum,0,sizeof(sum));
        n=read(),m=read();
        for(re i=1;i)
        {
            char ch;int a,b,c,d;
            cin>>ch;
            if(ch==C)
            {
                a=read(),b=read(),c=read(),d=read();
                add(a,b,1),add(c+1,d+1,1),add(a,d+1,-1),add(c+1,b,-1);
            }
            else
            {
                a=read(),b=read();
                printf("%d\n",Query(a,b)%2);
            }
        }
        puts("");
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

 

 

 3.区间修改,区间查询。

树状数组

标签:algorithm   printf   lib   print   nbsp   color   数组   main   math   

原文地址:https://www.cnblogs.com/Dxy0310/p/9749253.html


评论


亲,登录后才可以留言!