segment tree(2) - 이분탐색
int find(int val, int node, int x, int y)
{
if (x == y)
return x;
if (seg[node * 2] >= val)
return find(val, node * 2, x, (x + y) / 2);
else
return find(val - seg[node * 2], node * 2 + 1, (x + y) / 2 + 1, y);
}
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <cstring>
#include <stack>
#include <string>
#include <set>
#include <map>
#include <math.h>
#define INF 1000000000
using namespace std;
int n,m;
vector<long long > a;
vector<long long > seg;
long long init(int node ,int start , int end){
if(start == end){
return seg[node] = a[start];
}
int mid = (start + end) /2;
return seg[node] = init(node*2,start , mid) + init(node*2+1,mid+1 , end);
}
void update(int node , int x, int y , int index , long long diff){
if(index < x || index >y) return;
seg[node] += diff;
if(x != y){
int mid = (x+y)/2;
update(node*2 ,x,mid , index ,diff);
update(node*2+1 , mid+1 , y , index , diff);
}
}
int find(int val, int node, int x, int y)
{
if (x == y)
return x;
if (seg[node * 2] >= val)
return find(val, node * 2, x, (x + y) / 2);
else
return find(val - seg[node * 2], node * 2 + 1, (x + y) / 2 + 1, y);
}
int main(){
scanf("%d" , &n);
a.resize(n+2);
seg.resize(4*n);
for(int i=1;i<=n;i++){
scanf("%lld" , &a[i]);
}
init(1,1,n);
scanf("%d" ,&m);
int t1,t2,t3;
while(m--){
scanf("%d" , &t1);
if(t1 == 1){
scanf("%d %d" , &t2, &t3);
int diff = t3;
a[t2] +=t3;
update(1,1,n,t2,diff);
}else if(t1 == 2){
scanf("%d" , &t2);
printf("%d\n", find(t2, 1, 1, n));
}
}
}