首页 > 其他分享 >洛谷P3374 【模板】树状数组 1-(单点修改,区间查询)

洛谷P3374 【模板】树状数组 1-(单点修改,区间查询)

时间:2023-03-31 16:35:34浏览次数:41  
标签:输出 单点 数列 int cin add 区间 洛谷 P3374

题目描述

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

  • 将某一个数加上 x

  • 求出某区间每一个数的和

输入格式

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

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

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

  • 1 x k 含义:将第 x 个数加上 k

  • 2 x y 含义:输出区间 [x,y] 内每个数的和

输出格式

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

输入输出样例

输入 #1
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4
输出 #1
14
16

说明/提示

【数据范围】

对于 30% 的数据,1≤n≤8,1≤m≤10;
对于 70% 的数据,1≤n,m≤1e4;
对于 100%的数据,1≤n,m≤5e5。

数据保证对于任意时刻,a 的任意子区间(包括长度为 1 和 n 的子区间)和均在 [−2^31,2^31) 范围内。

样例说明:

故输出结果14、16

代码实现:

#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int N=5e5+5;
int a[N],tr[N];
int n,m;
int lowbit(int x){
    return x&-x;
}
void add(int x,int y){
    for(int i=x;i<=n;i+=lowbit(i))tr[i]+=y;
}
int query(int x,int y){
    int res=0;
    for(int i=y;i;i-=lowbit(i))res+=tr[i];
    for(int i=x-1;i;i-=lowbit(i))res-=tr[i];
    return res;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
    	add(i,a[i]);
	}
    while(m--){
        int x,y,z;
        cin>>x;
        if(x==1){
            cin>>y>>z;
            add(y,z);
        }else{
            cin>>y>>z;
            cout<<query(y,z)<<endl;
        }
    }
    return 0;
}

 

标签:输出,单点,数列,int,cin,add,区间,洛谷,P3374
From: https://www.cnblogs.com/hxss/p/17276620.html

相关文章

  • 洛谷P3368 【模板】树状数组 2-(区间修改,单点查询)
    题目描述如题,已知一个数列,你需要进行下面两种操作:将某区间每一个数加上 x;求出某一个数的值。输入格式第一行包含两个整数 N、M,分别表示该数列数字的个数和操作的总个数。第二行包含 N 个用空格分隔的整数,其中第 i 个数字表示数列第 i 项的初始值。接下来......
  • 洛谷 P5642 - 人造情感(换根 dp)
    想起来很轻松,写起来很酸爽的套路题。默认以\(1\)为根。先考虑怎么算单个\(f(u,v)\),我们定义一个连通块的权值为从该连通块中选出若干条点不相交的路径,选出的路径的权值之和的最大值。那么显然\(f(u,v)\)就是整棵树的权值\(-\)挖掉\((u,v)\)这条路径后各个连通块的权值之......
  • 洛谷9150题解
    考虑把\(i\tok_i\)连边,这样形成若干个环。考虑断环为链并且把链复制一份接到后面。考虑求出从一个点集开始拓展能够到达的点集\(S1_i\)。显然\(S1_i\)在环上是连续的,设\(r_i\)表示第\(i\)个节点拓展能得到的右端点。考虑每个节点\(i\)所在强连通分量的点集合\(S2\)。可以证明\(......
  • 洛谷P1036 选数
    1#include<bits/stdc++.h>2usingnamespacestd;3intn,k,a[25];4inthk;//这个是k个数加起来的和5intsum;//这个是个数(输出的那个)6intpdzhi(intx){......
  • 洛谷P1020
    P1020[NOIP1999普及组]导弹拦截思考这题很显然是一道DP题,第一问就是求该序列的最长不下降子序列.先说最长不下降子序列的\(O(n^2)\)的做法.用\(dp_k\)表示第\(k\)......
  • 数组模拟双向列表 洛谷 P1160 队列安排
    题目描述一个学校里老师要将班上N个同学排成一列,同学被编号为1~N,他采取如下的方法:1.先将1号同学安排进队列,这时队列中只有他一个人;2.2~N号同学依次入列,编号为i的同学入列方式......
  • 说说什么是单点登录?什么是SSO?什么是CAS?
    单点登录简介单点登录(SingleSignOn,SSO),就是通过用户的一次性鉴别登录。当用户在身份认证服务器上登录一次以后,即可获得访问单点登录系统中其他关联系统和应用软件的权限,......
  • 洛谷 P1967 货车运输
    P1967NOIP2013提高组]货车运输-洛谷|计算机科学教育新生态(luogu.com.cn)这个题目算是lca的稍微拓展吧。主要思考方向应该是很明显的。就是考虑一条路径上权值最......
  • 洛谷 P5979 [PA2014]Druzyny
    简要题意有\(n\)个人,把他们划分成尽可能多的区间,其中第\(i\)个人要求它所在的区间长度大于等于\(c_i\),小于等于\(d_i\),求最多的区间数量以及如此划分的方案数。数......
  • 洛谷P1115 最大子段和
    题目传送门题目描述给出一个长度为 n 的序列 a,选出其中连续且非空的一段使得这段和最大。输入格式第一行是一个整数,表示序列的长度 n。第二行有 n 个整数,第......