Segment tree 랑 Binary search 조합

특정 구간의 합을 정할때 ..사용하는 구조로 

다른 입력의 순위를 구할때 segment tree 사용

Segment tree + binary search

// function to build the tree
void build(int arr[])
{
    // insert leaf nodes in tree
    for (int i = 0; i<n; i++)
        tree[n + i] = arr[i];

    // build the tree by calculating parents
    for (int i = n - 1; i > 0; --i)
        tree[i] = tree[i << 1] + tree[i << 1 | 1];
}

// function to update a tree node
void updateTreeNode(int p, int value)
{
    // set value at position p
    tree[p + n] = value;
    p = p + n;

    // move upward and update parents
    for (int i = p; i > 1; i >>= 1){
        tree[i >> 1] = tree[i] + tree[i ^ 1];
        //tree[i >> 1] = tree[i] + tree[i - 1];

        //if ((i - 1) =! (i ^ 1))
        //    printf("Test \n");
        //printf("i==> %d \n i^1 ==> %d \n i +1 ==> %d \n" , i, i^1, i +1);
    }

}



// function to get sum on interval [l, r)
int query(int l, int r)
{
    int res = 0;

    // loop to find the sum in the range

    if (l == r)
        return tree[l + n];

    for (l += n, r += n; l < r; l >>= 1, r >>= 1)
    {
        if (l & 1)
            res += tree[l++];

        if (r & 1)
            res += tree[--r];
    }
    return res;
}


int  binarySearch(int low, int high, int target)
{
    int mid;
    int q_ans;

#if 1
    mid = (low + high) / 2;


    q_ans = query(low, mid + 1);

    if (target < q_ans){
        binarySearch(low, mid, target);
    }
    else if (q_ans < target)
    {
        target -= q_ans;

        if (target <= 0)
            return mid;
        else
            binarySearch(mid + 1, high, target);
    }
    else{
        //printf("TEst debug \n");
        return mid;
    }

#else

    ll l, r;
    l = low;
    r = high;
    unsigned int ans = 0x7fffffff;

    while (l <= r){

        mid = (l + r) / 2;
        q_ans = query(low, mid + 1);
        if (q_ans >= target){

            ans = MIN(ans, mid);
            r = mid - 1;
        }
        else l = mid + 1;
    }

    return ans;
#endif
}


void init()
{
    int i = 0, test = 0;
    int ans = 0;

    n = MAX_PRI;


    for (i = 0; i < MAX_PRI<<1; i++){
   
        arr[i] = tree[i] = 0;
    }

    lowest = 0x7fffffff;
    highest = 0;
   
#if 1
    // test //
    for (i = 1; i < 101; i++)
        updateTreeNode(i,  i);
   
    ans = 0;
    for (i = 1; i < 51; i++)
        ans += i;
   
    ans = query(1, 51);

    ans = binarySearch(1, 101, 1275);
    printf("Debug test %d \n", ans);

    ans = binarySearch(1, 101, 1274);
    printf("Debug test %d \n", ans);

    ans = binarySearch(1, 101, 1275 + 51);
    printf("Debug test %d \n", ans);
    printf("Debug test %d \n", ans);

#endif


}

void addReminderPlan(int priority, int count)
{
   
    arr[priority] += count;
    updateTreeNode(priority, arr[priority]);

    lowest  = MIN(lowest, priority);
    highest = MAX(highest, priority);

    //if (priority ==0 )
        //printf("Debug test zero \n");

}

void removeReminderPlan(int priority, int count)
{
    arr[priority] -= count;
    updateTreeNode(priority, arr[priority]);
}

int setCompleteReminderPlan(int priority)
{
     int ret = 0;

#if 0
     int test = 0;
     if (priority == 323){
         test = query(77, 208 +1);
         test = query(77, 208);
         

         test = query(77, 198 +1);
         test = query(77, 198);
     }
#endif

     ret = binarySearch(lowest, highest, priority);


     arr[ret]--;
     updateTreeNode(ret, arr[ret]);

     
     return ret;
}