Cod sursa(job #1985232)
Utilizator | Sorodoc Matei mateisoro | Data | 27 mai 2017 11:04:09 |
---|---|---|---|
Problema | Arbori indexati binar | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.02 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
const int N=100010;
int n,m,A[N];
void update (int p, int v)
{
for(int i=p;i<=n;i+=(i&(-i)))
A[i]+=v;
}
int suma (int p)
{
int s=0;
for(int i=p;i>0;i-=(i&(-i)))
s+=A[i];
return s;
}
int main()
{
f>>n>>m;
for(int i=1;i<=n;i++)
{
int x;
f>>x;
update(i,x);
}
for(;m;m--)
{
int a,b,c;
f>>c>>a;
if(c==2)
{
int st=0,dr=n,mi;
while(dr-st>1)
{
mi=(st+dr)/2;
if(suma(mi)<a)
st=mi;
else
dr=mi;
}
if(suma(dr)==a)
g<<dr<<'\n';
else
g<<-1;
continue;
}
f>>b;
if(c==0)
update(a,b);
else
g<<suma(b)-suma(a-1)<<'\n';
}
return 0;
}