# My C++ implemented segment tree base method with value discretization.

• My C++ implemented segment tree base method with value discretization.

``````typedef long long ll;
vector<ll> tree;
void TreeInsert(int rt, int l, int r,int pos){
if(l==r){
tree[rt]++;
return ;
}
int mid=(l+r)>>1;
if(pos<=mid){
TreeInsert(rt<<1, l, mid, pos);
}else{
TreeInsert(rt<<1|1, mid+1, r, pos);
}
tree[rt]++;
}
void TreeDelete(int rt, int l, int r, int pos){
if(l==r){
tree[rt]--;
return;
}
int mid=(l+r)>>1;
if(pos<=mid){
TreeDelete(rt<<1, l, mid, pos);
}else{
TreeDelete(rt<<1|1, mid+1, r, pos);
}
tree[rt]--;
}
int TreeFind(int rt, int l, int r, int L, int R){
if(l>=L&&r<=R){
return tree[rt];
}
if(r<L||l>R){
return 0;
}
int mid=(l+r)>>1;
int ret=0;
if(L<=mid){
ret+=TreeFind(rt<<1, l, mid, L, R);
}
if(R>mid){
ret+=TreeFind(rt<<1|1, mid+1, r, L, R);
}
return ret;
}
int countRangeSum(vector<int>& nums, int lower, int upper) {
vector<ll> sum(nums.size()+1, 0);
map<ll, int> mp;
for(int i=0; i<nums.size(); ++i){
sum[i+1]=sum[i]+nums[i];
mp[sum[i+1]]=1;
}
for(int i=0; i<sum.size(); ++i){
mp[lower+sum[i]]=1;
mp[upper+sum[i]]=1;
}
tree.resize(mp.size()<<2, 0);
int cnt=0;
for(map<ll, int>::iterator it=mp.begin(); it!=mp.end(); ++it){
it->second=++cnt;
}
for(int i=1; i<sum.size(); ++i){
TreeInsert(1, 1, cnt, mp[sum[i]]);
}
int ans=0;
for(int i=0; i<nums.size(); ++i){
int _lower_index=mp[lower+sum[i]],
_upper_index=mp[upper+sum[i]];
ans+=TreeFind(1, 1, cnt, _lower_index, _upper_index);
TreeDelete(1, 1, cnt, mp[sum[i+1]]);
}
cout<<INT_MAX<<"\t"<<INT_MIN<<endl;
return ans;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.