树状数组(差分用法)

#include<iostream>
#define ll long long
using namespace std;
const int N=1e6+10;
ll a[N], t[N];
ll n, m;
ll lowbit(int x)
{
	return x & -x;
}
void add(int x, int y)
{
	for(int i = x;i <= n;i += lowbit(i))t[i] += y;
}
void addd(int x,int y)
{
	for(int i = x;i <= n;i += lowbit(i))t[i] -= y;
}
ll qurry(int x)
{
	ll  res = 0;
	for(int i = x;i > 0;i -=lowbit(i))res += t[i];
	return res;
}
int main()
{
	
	cin >> n >> m;
	for(int i = 1;i <= n ;i ++)cin >> a[i];
	for(int i = 1;i <= n;i ++)
	{
		add(i, a[i] - a[i - 1]);
	}
	while(m --)
	{
		int k, x, y, z;
		cin >> k ;
		if(k == 1)
		{
		   cin >> x >> y >> z;
		   add(x, z);
		   addd(y + 1, z);
		}
		else{
			cin >> x;
           cout<<qurry(x)<<endl;		
		}
	}
}

全部评论

相关推荐

珩珺:那些经历都太大太空了,实习的情况不了解,大创项目连名字、背景、目的及意义都没体现出来;地摊经济更是看完连卖的什么产品都不知道,项目成果直接写营收多少都更直观真实一点;后面那个校文体部的更是工作内容是组织活动整理流程,成果变成了当志愿者,而且你们学校本科学生会大一入学就直接当部长吗,志愿里面还提到了疫情防控,全面解封是22年12月的事情,可能时间上也有冲突。可能你花了钱人家就用AI给你随便写了点内容改了一下,没什么体现个性化的点
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务