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);

}

이런식으로도 구현을 하더라 ... 

개쩐당 ... 

은 합을 구하는 문제인데 https://www.acmicpc.net/problem/1321

#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));

        

        }

    }

    

    

    

    

}