树状数组和线段树

标签：index right 树状 int 线段 tree 数组 include left

树状数组：简化线段树

作用：单点修改，单点查询，区间查询，区间修改

例题

链接　　P3374 【模板】树状数组 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

如题，已知一个数列，你需要进行下面两种操作：

将某一个数加上 �x
求出某区间每一个数的和

输入格式

第一行包含两个正整数 �,�n,m，分别表示该数列数字的个数和操作的总个数。

第二行包含 �n 个用空格分隔的整数，其中第 �i 个数字表示数列第 �i 项的初始值。

接下来 �m 行每行包含 33 个整数，表示一个操作，具体如下：

1 x k 含义：将第 �x 个数加上 �k
2 x y 含义：输出区间 [�,�][x,y] 内每个数的和

输出格式

输出包含若干行整数，即为所有操作 22 的结果。

输入输出样例

输入 #1

输出 #1

14
16
树状数组

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int n,m,tree[2000010];
int lowbit(int k)
{
    return k & -k;
}
void add(int x,int k)
{
    while(x<=n)
    {
        tree[x]+=k;
        x+=lowbit(x);
    }
}
int sum(int x)
{
    int ans=0;
    while(x!=0)
    {
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int a;
        scanf("%d",&a);
        add(i,a);
    }
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(a==1)
            add(b,c);
        if(a==2)
            cout<<sum(c)-sum(b-1)<<endl;
    }
}


线段树

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
int n,m;
int ans;
int he=0;
int input[500010];
struct node
{
    int left,right;
    int num;
}tree[2000010];
void build(int left,int right,int index)
{
    he++;
    tree[index].left=left;
    tree[index].right=right;
       if(left==right)
        return ;
    int mid=(right+left)/2;
    build(left,mid,index*2);
    build(mid+1,right,index*2+1);
}
int add(int index)
{
    if(tree[index].left==tree[index].right)
    {
        //cout<<index<<" "<<input[tree[index].right]<<endl;
        tree[index].num=input[tree[index].right];
        return tree[index].num;
    }
    tree[index].num=add(index*2)+add(index*2+1);
    return tree[index].num;
}
void my_plus(int index,int dis,int k)
{
    tree[index].num+=k;
    if(tree[index].left==tree[index].right)
        return ;
    if(dis<=tree[index*2].right)
        my_plus(index*2,dis,k);
    if(dis>=tree[index*2+1].left)
        my_plus(index*2+1,dis,k);
}
void search(int index,int l,int r)
{
    //cout<<index<<" ";
    if(tree[index].left>=l && tree[index].right<=r)
    {
        ans+=tree[index].num;
        return ;
    }
    if(tree[index*2].right>=l)
        search(index*2,l,r);
    if(tree[index*2+1].left<=r)
        search(index*2+1,l,r);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%d",&input[i]);
    build(1,n,1);
    add(1);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(a==1)
        {
            my_plus(1,b,c);
        }
        if(a==2)
        {
            ans=0;
            search(1,b,c);
            printf("%d\n",ans);
        }
    }
}

zkw线段树

#include<cstdio>
#define go(i,j,n,k) for(int i=j;i<=n;i+=k)
#define fo(i,j,n,k) for(int i=j;i>=n;i-=k)
#define mn 500010
#define ll long long
inline ll read()
{    int x=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0')
    {
        if(ch=='-')f=-f;ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';ch=getchar();
    }
    return x*f;
}

ll z[mn << 2], M, n, m;

void update(int rt)
{
    z[rt] = z[rt<<1] + z[rt<<1|1];
}

void build()
{
    for(M=1;M<n+2;M<<=1);go(i,M+1,M+n,1)z[i]=read();fo(i,M,1,1) update(i);
}

void modify(int now,ll v)
{
    for(z[now+=M]+=v,now>>=1;now;now>>=1)update(now);
}

ll query(int l,int r)
{
    int ans=0;
    for(--l+=M,++r+=M;l^r^1;l>>=1,r>>=1)
    {
        if(~l&1)ans+=z[l^1];if(r&1)ans+=z[r^1];
    }
    return ans;
}

int main()
{
    n=read(),m=read();build();
    go(i,1,m,1)
    {
        int s=read(),x=read(),y=read();
        if(s==1)modify(x,y);else printf("%lld\n",query(x,y));
    }
}

标签：index,right,树状,int,线段,tree,数组,include,left
From： https://www.cnblogs.com/weinan030416/p/17060144.html

题目描述

输入格式

输出格式

输入输出样例

相关文章

赞助商

阅读排行