I studied segment tree recently and I made this code of segment tree and its queries. Is my code correct in terms of time complexity?
class segmentTree{
private:
vector<int> mini;
vector<int> tree;
vector<int> maxi;
int n;
Here in the constructor I passed the dynamic array.
public:
segmentTree(vector<int> a)
{
mini=a;
tree=a;
maxi=a;
n=tree.size();
}
makeTree function builds three segment trees for different queries like sum, maximum and minimum.
void makeTree()
{
reverse(tree.begin(),tree.end());
reverse(mini.begin(),mini.end());
reverse(maxi.begin(),maxi.end());
for(int i=0;i<tree.size();i+=2)
{
tree.pb(tree[i]+tree[i+1]);
mini.pb(min(mini[i],mini[i+1]));
maxi.pb(max(maxi[i],maxi[i+1]));
}
tree.PB();
mini.PB();
maxi.PB();
reverse(tree.begin(),tree.end());
reverse(mini.begin(),mini.end());
reverse(maxi.begin(),maxi.end());
}
The sum function calculates the sum of given range.
int sum(int a,int b)
{
a+=(n);
b+=(n);
int sum=0;
while(a<=b)
{
if(a%2==1)
{
sum+=tree[a-1];
a++;
}
if(b%2==0)
{
sum+=tree[b-1];
b--;
}
a/=2;
b/=2;
}
return sum;
}
The minimum function finds the minimum value of given range.
int minimum(int a,int b)
{
a+=(n);
b+=(n);
int minu;
while(a<=b)
{
if(a%2==1)
{
minu=mini[a-1];
a++;
}
if(b%2==0)
{
minu=mini[b-1];
b--;
}
a/=2;b/=2;
}
return minu;
}
The maximum function finds the maximum value of given range.
int maximum(int a,int b)
{
a+=(n);
b+=(n);
int maxu;
while(a<=b)
{
if(a%2==1)
{
maxu=maxi[a-1];
a++;
}
if(b%2==0)
{
maxu=maxi[b-1];
b--;
}
a/=2;b/=2;
}
return maxu;
}
};
vector
andreverse
from the standard library, or written by yourself?std::vector
does not have a member function namedpb()
orPB()
, so if it is a custom class you should include it as well. \$\endgroup\$