BIT

毎回こんがらがるのでメモ.自分用なので読んでも意味ないよ.(それどころか悪影響かも)
segtreeの右の子を全部消したような奴(左から累積和を取るのに兄弟をふたりとも使うことはないので)

1=1
2=2
3=2+1
4=4
5=4+1
6=4+2
7=4+2+1
8=8
みたいになるので1-indexedが楽.
上の式で最後に足された項に対応する区間にindexとしてその数字を与える(ちゃんとZ+と全単射になる).

sum:
[1,x]のsumは,LSBから1をどんどん消していったものの所を足す
sum[1,7]=bit[7]+bit[6]+bit[4]
sum[1,5]=bit[5]+bit[4]
sum[1,1]=bit[1]
一番低い1はi&-iで取り出せる(unary-がちゃんと優先順位高い)

i =010010100
~i=101101011
-i=101101100

コードは,

int sum(int i){	//[1,i] 1-indexed
	int s=0;
	while(i>0){
		s+=bit[i];
		i-=(i&-i);
	}
	return s;
}

add:
iを含む区間を列挙する
1:1,2,4,8
2:2,4,8
3:3,4,8
4:4,8
5:5,6,8
6:6,8
7:7,8
8:8
こっちは逆に,iから一番低い1を足していけばOK.

void add(int i,int x,int N){	//N:もともと何箇所あるか(上の図なら8)
	while(i<=N){
		bit[i]+=x;
		i+=(i&-i);
	}
	return;
}

Nは2べきじゃなくてもいい(なぜなら,addでNより大きいindexのところに足されなくなるだけでN以下に対しては同じ動きをする,sumも同じ動きをする)
使い方:
0~1145141919までの数がN<=100000個与えられる.途中で[l,r]に数は何個ありますかみたいなクエリが来る.答えて.

全部読み込んで座標圧縮.indexは0からになる.

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
const int MAX_N=100000;
int Q,t[MAX_N],l[MAX_N],r[MAX_N],bit[MAX_N+1];
vector<int> ash;
int sum(int i){
	int s=0;
	while(i>0){
		s+=bit[i];
		i-=(i&-i);
	}
	return s;
}
void add(int i,int v,int N){
	while(i<=N){
		bit[i]+=v;
		i+=(i&-i);
	}
}
int main(){
	cin>>Q;
	rep(i,Q) cin>>t[i]>>l[i]>>r[i];
	rep(i,Q) if(t[i]==0) ash.pb(l[i]);
	sort(all(ash));
	ash.erase(unique(all(ash)),ash.end());
	int M=ash.size();
	rep(i,Q){
		if(t[i]==0){
			int id=lower_bound(all(ash),l[i])-ash.begin();		//0-indexed!!
			add(id+1,1,M);
		}else{
			int lid=lower_bound(all(ash),l[i])-ash.begin();		//l[i]以上最小(ないならN)
			int rid=upper_bound(all(ash),r[i])-ash.begin()-1;	//r[i]以下最大(ないなら-1)
			//↑ 0-indexed
			cout<<sum(rid+1)-sum(lid+1-1)<<endl;
		}
	}
}

これ難しいんですよ、難しくないですか?こういうindex系は本当に苦手でいつもめちゃくちゃ時間がかかります.こういうの上位陣の人は一瞬で書くのに,自分はバグらせちゃって30分ロスるとかザラです.
どこが難しいかというと,0-indexedと1-indexedが混在していることで,しかもどっちにもそれなりの利点があることです.
0:座標圧縮したんだから自然.lower_boundなども当然こっちで返してくる.
1:BITが使いやすい.sum(0)=0になって直感的.

実装に自由度があると迷ったりバグらせたりするので直感的な方に決めてしまおう.
sum(x)=x個の和を返す わかりやすい これは今のままでいいですね(1-indexedの利点)
add(x) これ1-indexed直感に反しますね,やっぱり配列は0~N-1と思いたい.BIT使わずにやるとした時と似た処理になりますよね.
というわけで,これからはこっちを使います.こっちしか使いません.今決めた.

int bit[N+1];		//Nは区間幅!!!
int sum(int x){		//x個の和[0,x)
	int s=0;
	while(i>0){
		s+=bit[i];
		i=(i&(i-1));
	}
	return s;
}
void add(int i,int x,int N){	//a[i]+=x (0-indexed)
	i++;
	while(i<=N){
		bit[i]+=x;
		i+=(i&-i);
	}
}