线段树&树状树组

时间：2021-09-18 19:20:41

线段树

单点修改，区间查询

#include<bits/stdc++.h>

using namespace std;

int n,q;
long long num[1000010];

struct tree
{
    int l,r;
    long long sum,max;
}t[4000010];

void BuildTree(int,int,int);

void Update(int,int,int,int,long long);

long long Query(int,int,int,int,int);

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%lld",num+i);
    BuildTree(1,1,n);
    for(int i=1;i<=q;i++)
    {
        int c;
        scanf("%d",&c);
        if(c==1)
        {
            int a;
            long long b;
            scanf("%d%lld",&a,&b);
            Update(1,1,n,a,b);
        }
        else
        {
            int a,b;
            scanf("%d%d",&a,&b);
            printf("%lld\n",Query(1,1,n,a,b));
        }
    }
return 0;
}

void BuildTree(int id,int l,int r)
{
    int mid=(l+r)>>1;
    t[id].l=l;
    t[id].r=r;
    if(l==r)
    {
        t[id].sum=t[id].max=num[l];
        return;
    }
    BuildTree(id*2,l,mid);
    BuildTree(id*2+1,mid+1,r);
    t[id].sum=t[id*2].sum+t[id*2+1].sum;
//  t[id].max=max(t[id*2].max,t[id*2+1].max);
}

void Update(int id,int l,int r,int x,long long v)
{
    int mid=(l+r)>>1;
    if(l==r&&l==x)
    {
        t[id].sum+=v;
//      t[id].max+=v;
        return;
    }
    if(mid<x)
    {
        Update(id*2+1,mid+1,r,x,v);
    }
    else 
    {
        Update(id*2,l,mid,x,v);
    }
    t[id].sum=t[id*2].sum+t[id*2+1].sum;
    //t[id].max=max(t[id*2].max,t[id*2+1].max);
}

long long Query(int id,int l,int r,int x,int y)
{
    int mid=(l+r)>>1;
    long long sum=0;
    if(x<=l&&y>=r)return t[id].sum;
    if(x<=mid)sum+=Query(id*2,l,mid,x,y);
    if(y>mid)sum+=Query(id*2+1,mid+1,r,x,y);
    return sum;
}

区间修改，单点查询

#include<bits/stdc++.h>

#define lson id*2,l,mid
#define rson id*2+1,mid+1,r

using namespace std;

int n,q;
int num[1000010];

struct node
{
    int l,r;
    int addmark;
    long long sum;
}tree[4000010];

void BuildTree(int,int,int);

long long Query(int,int,int,int);

void UpDate(int,int,int,int,int,long long);

void PushDown(int);

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",num+i);
    }
    BuildTree(1,1,n);
    for(int i=1;i<=q;i++)
    {
        int k;
        scanf("%d",&k);
        if(k==1)
        {
            int t,p;
            long long v;
            scanf("%d%d%lld",&t,&p,&v);
            UpDate(1,1,n,t,p,v);
        }
        if(k==2)
        {
            int t;
            scanf("%d",&t);
            printf("%lld\n",Query(1,1,n,t));
        }
    }
return 0;
}

void BuildTree(int id,int l,int r)
{
    tree[id].l=l;
    tree[id].r=r;
    if(l==r)
    {
        tree[id].sum=num[l];
        return;
    }
    int mid=(l+r)>>1;
    BuildTree(lson);
    BuildTree(rson);
    tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
}

long long Query(int id,int l,int r,int x)
{
    if(l==r&&l==r)
    {
        return tree[id].sum;
    }
    PushDown(id);
    int mid=(l+r)>>1;
    if(x<=mid)return Query(lson,x);
    else if(x>mid)return Query(rson,x);
}

void UpDate(int id,int l,int r,int x,int y,long long val)
{
    if(x<=l&&y>=r)
    {
        tree[id].sum+=val*(l-r+1);
        tree[id].addmark+=val;
        return;
    }
    PushDown(id);
    int mid=(l+r)>>1;
    if(x<=mid)UpDate(lson,x,y,val);
    if(y>mid)UpDate(rson,x,y,val);
    tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
}

void PushDown(int id)
{
    if(tree[id].addmark!=0)
    {
        tree[id*2].sum+=tree[id].addmark*(tree[id*2].r-tree[id*2].l+1);
        tree[id*2+1].sum+=tree[id].addmark*(tree[id*2+1].r-tree[id*2+1].l+1);
        tree[id*2].addmark+=tree[id].addmark;
        tree[id*2+1].addmark+=tree[id].addmark;
        tree[id].addmark=0;
    }
}

区间修改，区间查询

#include<bits/stdc++.h>

using namespace std;

int n,q;
long long num[1000010];

struct tree
{
    int l,r;
    long long sum,addmark;
}t[4000010];

void BuildTree(int,int,int);

void Update(int,int,int,int,int,long long);

long long Query(int,int,int,int,int);

void PushDown(int);

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%lld",num+i);
    BuildTree(1,1,n);
    for(int i=1;i<=q;i++)
    {
        int o;
        scanf("%d",&o);
        if(o==1)
        {
            int a,b;
            long long c;
            scanf("%d%d%lld",&a,&b,&c);
            Update(1,1,n,a,b,c);
        }
        else
        {
            int a,b;
            scanf("%d%d",&a,&b);
            printf("%lld\n",Query(1,1,n,a,b));
        }
    }
return 0;
}

void BuildTree(int id,int l,int r)
{
    int mid=(l+r)>>1;
    t[id].l=l;
    t[id].r=r;
    if(l==r)
    {
        t[id].sum=num[l];
        return;
    }
    BuildTree(id*2,l,mid);
    BuildTree(id*2+1,mid+1,r);
    t[id].sum=t[id*2].sum+t[id*2+1].sum;
}

void Update(int id,int l,int r,int x,int y,long long v)
{
    int mid=(l+r)>>1;
    if(x<=l&&y>=r)
    {
        t[id].sum+=v*(r-l+1);
        t[id].addmark+=v;
        return;
    }
    PushDown(id);
    if(x<=mid)Update(id*2,l,mid,x,y,v);
    if(y>mid)Update(id*2+1,mid+1,r,x,y,v);
    t[id].sum=t[id*2].sum+t[id*2+1].sum;
}

long long Query(int id,int l,int r,int x,int y)
{
    int mid=(l+r)>>1;
    long long sum=0;
    if(x<=l&&y>=r)return t[id].sum;
    PushDown(id);
    if(x<=mid)sum+=Query(id*2,l,mid,x,y);
    if(y>mid)sum+=Query(id*2+1,mid+1,r,x,y);
    return sum;
}

void PushDown(int id)
{
    if(t[id].addmark!=0)
    {
        t[id*2].addmark+=t[id].addmark;
        t[id*2+1].addmark+=t[id].addmark;
        t[id*2].sum+=t[id].addmark*(t[id*2].r-t[id*2].l+1);
        t[id*2+1].sum+=t[id].addmark*(t[id*2+1].r-t[id*2+1].l+1);
        t[id].addmark=0;
    }
}

树状数组

单点修改，区间查询

#include<bits/stdc++.h>

#define lowbit id&-id

using namespace std;

int n,q;
int tree[1000010];

long long Query(int);

void Add(int,int);

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i)
    {
        int a;
        scanf("%d",&a);
        Add(i,a);
    }
    for(int i=1;i<=q;++i)
    {
        int c;
        scanf("%d",&c);
        if(c==1)
        {
            int x,k;
            scanf("%d%d",&x,&k);
            Add(x,k);
        }
        if(c==2)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%lld\n",Query(y)-Query(x-1));
        }
    }
return 0;
}

void Add(int id,int x)
{
    while(id<=n)
    {
        tree[id]+=x;
        id+=lowbit;
    }
}

long long Query(int id)
{
    long long sum=0;
    while(id>=1)
    {
        sum+=tree[id];
        id-=lowbit;
    }
return sum;
}

区间修改，单点查询

不会

标签：

相关文章