- 树状数组 2 :区间修改,单点查询
题解
- 2024-5-30 21:57:16 @
#include
#define int long long
using namespace std;
const int maxn=1e6+10;
int n,m,opr,x,y,k;
int c[maxn],a[maxn];
inline int read()
{
int ans=0;
char last=' ',ch=getchar();
while(ch<'0'||ch>'9') last=ch,ch=getchar();
while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}
int lowbit(int x)
{
return x&-x;
}
void updata(int x,int v)
{
while(x<=n)
{
c[x]+=v;
x+=lowbit(x);
}
}
int sum(int x)
{
int ans=0;
while(x>0)
{
ans+=c[x];
x-=lowbit(x);
}
return ans;
}
signed main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
updata(i,a[i]-a[i-1]);
}
for(int i=1;i<=m;i++)
{
opr=read();
if(opr==1)
{
x=read();y=read();k=read();
updata(x,k);
updata(y+1,-k);
}
if(opr==2)
{
x=read();
printf("%lld\n",sum(x));
}
}
return 0;
}
0 条评论
目前还没有评论...
信息
- ID
- 2611
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 102
- 已通过
- 20
- 上传者