首页 > 其他分享 >F - 树状数组 2【GDUT_22级寒假训练专题五】

F - 树状数组 2【GDUT_22级寒假训练专题五】

时间:2023-02-19 12:22:59浏览次数:68  
标签:GDUT 单点 22 树状 int 差分 数组 include

F - 树状数组 2

原题链接

思路

在树状数组1中我们可以得知

  • 单点修改,区间查询(区间和)
    对原数组进行单点修改,对区间和进行树状数组维护

利用差分和前缀和我们可以推导出

  • 区间修改(差分),单点查询
    原数组 = 差分的前缀和数组
    对差分数组进行单点修改实现区间修改,对差分的前缀和数组(即原数组)进行树状数组维护实现单点查询

代码

点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;

#define X first
#define Y second

typedef pair<int,int> pii;
typedef long long LL;
const char nl = '\n';
const int N = 5e5+10;
const int M = 2e5+10;
int n,m;
LL a[N],d,b[N];

int lowbit(int x){
	return x & -x;
}

void add(int k,int x){
	while(k <= n){
		b[k] += x;
		k += lowbit(k);
	}
}

LL getsum(int l,int r){
	l --;
	LL s1 = 0;
	while(l){
		s1 += b[l];
		l -= lowbit(l);
	}
	LL s2 = 0;
	while(r){
		s2 += b[r];
		r -= lowbit(r);
	}
	return s2 -s1;
}
void solve(){
	cin >> n >> m;
	for(int i = 1; i <= n; i ++ ){
		cin >> a[i];		//原数组
		d = a[i] - a[i-1];	//差分数组
		add(i,d);	//对差分数组的前缀和进行树状数组维护
	}
	while(m --){
		int op;
		cin >> op;
		if(op == 1){
			int l,r,x;
			cin >> l >> r >> x;
			add(l,x);	//差分
			add(r+1,-x);	//差分
		}
		else{	//输出s[k]差分数组(1,k)的和
			int k;
			cin >> k;
			cout << getsum(1,k) << nl;	
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	solve();
}

标签:GDUT,单点,22,树状,int,差分,数组,include
From: https://www.cnblogs.com/J-12045/p/17134513.html

相关文章

  • E - 树状数组 1【GDUT_22级寒假训练专题五】
    E-树状数组1原题链接题意已知一个数列,你需要进行下面两种操作:将某一个数加上\(x\)求出某区间每一个数的和lowbit函数定义一个函数\(f=lowbit(x)\),这个函......
  • 2022.2.19闲话
    00:46:就是感觉最近都没什么干劲,学校里的课业知识是真的不太想学,除了数学以外的学科都是大折磨。不懂但是还要搞,是因为对我而言很痛苦但是对其他人类来说并不一定如此。啊......
  • B - Learning Languages【2022级专题三图论课后练习】
    B-LearningLanguages原题链接思路由于可以传译,所以可以将共同语言(包括传译)者视为一个集合(合并),最后查询总共集合数-1就是答案注意特判:有可能有公司所有人一种语言都......
  • A - 并查集【2022级专题三图论课后练习】
    A-并查集思路模板注意01串的处理代码点击查看代码#include<iostream>usingnamespacestd;#defineXfirst#defineYsecondtypedefpair<int,int>pii;......
  • B - 滑雪【2022GDUT寒假集训-简单DP】
    B-滑雪原题链接思路\(定义f(i,j)为从坐标(i,j)出发的最大值\)\(状态转移方程f(i,j)=max(f(i+dx[k],j+dy[k]))\)\(答案为max(f(1,1),f(1,2),...,f(n,m))\)注意......
  • A - 摆花【2022GDUT寒假集训-简单DP】
    摆花原题链接思路\(\text{有}n\text{个数}\left(c_{1},c_{2},\ldots,c_{n}\right),0\leqslantc_{i}\leqslanta_{i}\text{,求有多少种方案数使}\s......
  • gym102222I(冒泡排序的性质)
    神必结论:设原序列为\(a\),新序列为\(a'\)冒泡排序\(k\)轮,之后\(a'\)第\(i\)项是\(a\)前\(\min(i+k,n)\)项里未在\(a'\)的前\(i-1\)项里出现的最小值换句话说,按顺序确定\(a......
  • 【专题】2022智能汽车云服务白皮书报告PDF合集分享(附原数据图表)
    报告链接:http://tecdat.cn/?p=31515原文出处:拓端数据公众号汽车和互联网技术产业的新生力量已经吹响了变革的号角,它们在争夺人心。传统汽车制造商也受益于这一趋势,获得了......
  • 【专题】2022新能源汽车品牌KOL口碑报告PDF合集分享(附原数据图表)
    报告链接:http://tecdat.cn/?p=31600原文出处:拓端数据部落公众号受产业政策、市场环境、消费者认知、产业技术等因素的驱动,近年来中国新能源汽车产业进入快速扩张阶段。据......
  • django连接ubuntu22下的mysql8
    1.安装mysql(这里就不过多赘述了)sudoapt-getinstallmysql-server  2.登录mysql  (1)在根目录/etc/mysql/debian.cnf,使用默认账户密码登录   (2)空密码......