Pagini recente » Borderou de evaluare (job #297142) | Rezultatele filtrării | Rezultatele filtrării | Cod sursa (job #2495836)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
#define cin fin
#define cout fout
/*
*/
const int NMAX=1e5+10;
int n, m, a, b, cond;
int bitree[NMAX];
int length;
int getNext(int index)
{
return index+(index&-index);
}
int getParent(int index)
{
return index-(index&-index);
}
void add(int index, int val)
{
index++;
while(index<length)
{
bitree[index]+=val;
index=getNext(index);
}
}
int sum(int index)
{
index++;
int suma=0;
while(index>0)
{
suma+=bitree[index];
index=getParent(index);
}
return suma;
}
int findsum(int suma, int left, int right)
{
if(left>right)
return -1;
int mij=(left+right)/2;
int auxsum=sum(mij);
if(auxsum==suma)
return mij;
if(auxsum>suma)
return findsum(suma, left, mij-1);
return findsum(suma, mij+1, right);
}
int main()
{
cin>>n>>m;
length=n+2;
for(int i=1; i<=n; i++)
{
cin>>b;
add(i, b);
}
for(int i=1; i<=m; i++)
{
cin>>cond;
if(cond==0)
{
cin>>a>>b;
add(a, b);
}
else
if(cond==1)
{
cin>>a>>b;
cout<<sum(b)-sum(a-1)<<"\n";
}
else
if(cond==2)
{
cin>>a;
cout<<findsum(a, 1, n)<<"\n";
}
}
return 0;
}