URL: https://ide.codingblocks.com/s/115109
I have constructed a segment tree in which each node has the minimum value of its range. The logic behind it is that if a value is less than the node’s value, then i will return the number of elements present in the given range…
dont pass array or vector during recursive call it takes time. And you should know start following a generic segment tree code if you have understood segment tree properly…
i am providing you my generic segment tree code… now start using this and make changes in merge function…If you are are having any doubt ask me…
sorry saumya for late reply … you are getting run error because of of skipping return statement. but wait you will get wrong answer after this beacuse of your logic try finding error in your logic or share your approach.
if (ss >= l && se <= r) {
node t = tree[index];
if (t.data >= value) {
int val = t.smallestAmong;
return val;
}
return 0;
}I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
#include<bits/stdc++.h>
using namespace std;
#define l long long int
typedef struct items{
vector v;
}item;
l binary_sea(vector v , l x)
{
//for(int i=0;i<v.size();i++)
//{
// cout<<v[i]<<" ";
//}
//cout<<endl;
l s = 0 , e = v.size()-1;
l an = -1;
while(s<=e)
{
l mid = (s+e)/2;
if(v[mid] < x)
{
s = mid+1;
}
else
{
e = mid-1;
an = mid;
}
}
if(an == -1)
{an = v.size();}
//cout<<v.size()-an<<" ";
return v.size()-an;
}
vector merge(vector x1 , vector x2)
{
for(unsigned l i=0;i<x2.size();i++)
{
x1.push_back(x2[i]);
}
sort(x1.begin(), x1.end());
return x1;
}
void build(item *tree , l ss , l se ,l a[] , l index)
{
if(ss == se)
{
vector s;
s.push_back(a[ss]);
tree[index] = {s};
return ;
}
l mid = (ss+se)/2;
build(tree , ss , mid ,a, 2*index);
build(tree , mid+1 , se ,a, 2*index+1);
tree[index] = {merge(tree[2*index].v , tree[2*index+1].v)};
return ;
}
int query(item *tree , l ss , l se , l x , l y ,l an , l index )
{
if(x>y or x>se or y<ss)
{
return 0;
}
if(x<=ss and y>=se)
{
vector<l> ::iterator it;
it = lower_bound(tree[index].v.begin() ,tree[index].v.end() , an);
return tree[index].v.size() - (it-tree[index].v.begin());
}
l mid = (ss+se)/2;
l left = query(tree , ss , mid , x , y , an , 2*index);
l right = query(tree , mid+1 , se , x , y , an , 2*index+1);
return left + right;
}
int main() {
int n;
cin>>n;
l a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
item tree[4*n+1];
build(tree , 0 , n-1 , a , 1);
/*
for(int i=0;i<4*n+1;i++)
{
for(int ch :tree[i].v)
{
cout<<ch<<" ";
}
cout<<endl;
}
*/
l m;
cin>>m;
l q,x,y;
while(m--)
{
cin>>q>>x>>y;
cout<<query(tree, 0 , n-1 , q-1 , x-1 ,y, 1)<<endl;
}
return 0;
}
i got run timr error in this problem