树状数组：单点修改，区间查询

2020-12-13 14:28

阅读：369

标签：mem name problems 水平 geo str 树状 while php

本人水平有限，题解不到为处，请多多谅解

本蒟蒻谢谢大家观看

题目：

Problem E: 树状数组 1 ：单点修改，区间查询

Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 231 Solved: 78
[Submit][Status][Web Board]

Description

给定数列
a[1],a[2],…,a[n]，你需要依次进行 q个操作，操作有两类：
1 i x：给定 i,x将 a[i]加上 x；
2 l r：给定 l,r，求a[l]+a[l+1]+?+a[r] 的值）。

Input

第一行包含 2 个正整数 n,q，表示数列长度和询问个数。保证 1≤n,q≤10^6 。
第二行 n 个整数a[1],a[2],…,a[n]，表示初始数列。保证 ∣a[i]∣≤10^6
接下来 q 行，每行一个操作，为以下两种之一：
1 i x：给定 i,x，将 a[i] 加上 x；
2 l r：给定 l,r，
保证 1≤l≤r≤n∣x∣≤10^6

Output

对于每个 2 l r 操作输出一行，每行有一个整数，表示所求的结果。

Sample Input

Sample Output

HINT

模板树状数组

code:

#include#pragma GCC optimize(3)
using namespace std;
typedef long long LL;
const int maxn=1e6+5;
int n,Q;
LL c[maxn];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch==‘-‘)f=-1;ch=getchar();}
    while(isdigit(ch)) {x=(x1)+(x3)+(ch^48);ch=getchar();}
    return x*f;
}
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int w)//在x位置加上w
{
    while(xn){
        c[x]+=w;
        x+=lowbit(x);//全部有关的集合都加上
    }
}
LL get(int x)//求区间A[1~x]的和return sum(r)-sum(l-1)
{
    LL cnt=0;
        while(x){
            cnt+=c[x];//先加上小区间 
            x-=lowbit(x);//再加上(大区间减去小区间的值) 
        }
    return cnt;
}
int main()
{
    n=read();Q=read();
    for(int i=1;i)
        add(i,read());
    while(Q--)
    {
        int id=read(),x=read(),y=read();
        if(id==1)
            add(x,y);
        if(id==2)
            printf("%lld\n",get(y)-get(x-1));
    }
    return 0;
}

树状数组：单点修改，区间查询

标签：mem name problems 水平 geo str 树状 while php

原文地址：https://www.cnblogs.com/nlyzl/p/11562254.html

上一篇：php getallheaders使用注意事项

下一篇：第一个MVC模式的程序

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：树状数组：单点修改，区间查询
文章链接：http://soscw.com/essay/34148.html

亲，登录后才可以留言！

树状数组：单点修改，区间查询

Problem E: 树状数组 1 ：单点修改，区间查询

Description

Input

Output

Sample Input

Sample Output

HINT

评论

热门文章

推荐文章

最新文章

置顶文章

树状数组 ：单点修改，区间查询

Problem E: 树状数组 1 ：单点修改，区间查询

Description

Input

Output

Sample Input

Sample Output

HINT

评论

热门文章

推荐文章

最新文章

置顶文章

树状数组：单点修改，区间查询