洛谷 P2068 统计和

题目描述

给定一个长度为n（n<=100000），初始值都为0的序列，x(x<=10000)次的修改某些位置上的数字，每次加上一个数，然后提出y (y<=10000)个问题，求每段区间的和。时间限制1秒。

输入输出格式

输入格式：

第一行1个数，表示序列的长度n

第二行1个数，表示操作的次数w

后面依次是w行，分别表示加入和询问操作

其中，加入用x表示，询问用y表示

x的格式为"x a b" 表示在序列a的位置加上b

y的格式为"y a b" 表示询问a到b区间的加和

输出格式：

每行一个数，分别是每次询问的结果

输入输出样例

输入样例#1：

输出样例#1：

8

17

线段树版题
区间求和 
单点修改 
屠龙宝刀点击就送

#include <iostream>

#include <cstdio>

using namespace std;

#define Max 200000

struct node

{

    int l,r,dis;

}tree[Max*];

int t=,n,w;

char cz;

void up(int k)

{

    tree[k].dis=tree[k<<].dis+tree[k<<|].dis;

}

void build(int l,int r,int k)

{

    tree[k].l=l;tree[k].r=r;

    if(l==r)

    {

        tree[k].dis=;

        return;

    }

    int mid=(l+r)>>;

    build(l,mid,k<<);

    build(mid+,r,k<<|);

    up(k);

}

void add(int to,int v,int k)

{

    if(tree[k].l==tree[k].r)

    {

        tree[k].dis+=v;

        return;

    }

    int mid=(tree[k].l+tree[k].r)>>;

    if(to<=mid) add(to,v,k<<);

    else add(to,v,k<<|);

    up(k);

}

int ans=;

void query(int u,int v,int k)

{

    if(tree[k].l==u&&tree[k].r==v)

    {

        ans+=tree[k].dis;

        return ;

    }

    int mid=(tree[k].l+tree[k].r)>>;

    if(mid>=v) query(u,v,k<<);

    else if(mid<u) query(u,v,k<<|);

    else query(u,mid,k<<),query(mid+,v,k<<|);

}

int main()

{

    scanf("%d",&n);

    build(,n,);

    scanf("%d",&w);

    int u,v;

    while(w--)

    {

        cin>>cz;

        scanf("%d%d",&u,&v);

        if(cz=='x')

        add(u,v,);

        else if(cz=='y')

        {

            ans=;

            query(u,v,);

            printf("%d\n",ans);

        }

    }

    return ;

}

巴特西

洛谷 P2068 统计和

题目描述

输入输出格式

输入输出样例

最新文章

热门文章