12345678910111213141516171819202122232425262728293031323334353637383940 |
- #include <iostream>
- using namespace std;
- #define LOGSZ 17
- int tree[(1<<LOGSZ)+1];
- int N = (1<<LOGSZ);
- // add v to value at x
- void set(int x, int v) {
- while(x <= N) {
- tree[x] += v;
- x += (x & -x);
- }
- }
- // get cumulative sum up to and including x
- int get(int x) {
- int res = 0;
- while(x) {
- res += tree[x];
- x -= (x & -x);
- }
- return res;
- }
- // get largest value with cumulative sum less than or equal to x;
- // for smallest, pass x-1 and add 1 to result
- int getind(int x) {
- int idx = 0, mask = N;
- while(mask && idx < N) {
- int t = idx + mask;
- if(x >= tree[t]) {
- idx = t;
- x -= tree[t];
- }
- mask >>= 1;
- }
- return idx;
- }
|