bit.sublime-snippet

<snippet>
	<content><![CDATA[
struct BIT{//use one based indexing
	int N;
	vector<int> bit;

	void init(int n){
		N = n;
		bit.assign(n + 10, 0);
	}

	void update(int idx, int val){
		while(idx <= N){
			bit[idx] += val;
			idx += idx & -idx;
		}
	}

	int pref(int idx){
		int ans = 0;
		while(idx > 0){
			ans += bit[idx];
			idx -= idx & -idx;
		}
		return ans;
	}

	int rsum(int l, int r){
		return pref(r) - pref(l - 1);
	}

	int kthOrder(int k){
		int cur = 0,sum = 0, ExtraSize = N + 1;
		int ln = log2(ExtraSize);
		for(int i = ln;i >= 0 ; --i){
			int temp = cur + (1 << i);
			if(temp <= ExtraSize && (sum + bit[temp]) < k){
				cur = temp;
				sum += bit[temp];
			}
		}
		if(cur == ExtraSize){
			return 0;
		}
		return cur + 1;
	}

	//one based indexing
	int lower_bound(int val){
		return (pref(val - 1) + 1);
	}

	//one based indexing
	int upper_bound(int val){
		return (pref(val) + 1);
	}
};
]]></content>
	<!-- Optional: Set a tabTrigger to define how to trigger the snippet -->
	<tabTrigger>bit</tabTrigger>
	<!-- Optional: Set a scope to limit where the snippet will trigger -->
	<!-- <scope>source.python</scope> -->
</snippet>