1
\$\begingroup\$

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;
    }
};
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Welcome to the Code Review Community. It is very difficult to see where the class ends and the code doesn't look complete. Can you please post the code as it is in your IDE or editor. \$\endgroup\$
    – pacmaninbw
    Commented Nov 26, 2020 at 15:15
  • 3
    \$\begingroup\$ correct in terms of time complexity? Are you asking whether this has a low time complexity? What do you think it is now? \$\endgroup\$
    – Reinderien
    Commented Nov 26, 2020 at 15:21
  • 2
    \$\begingroup\$ Are vector and reverse from the standard library, or written by yourself? std::vector does not have a member function named pb() or PB(), so if it is a custom class you should include it as well. \$\endgroup\$
    – G. Sliepen
    Commented Nov 26, 2020 at 16:36
  • \$\begingroup\$ pb() is for push_back() and PB() is pop_back(). I defined them as a macros. \$\endgroup\$ Commented Nov 27, 2020 at 9:29
  • \$\begingroup\$ "I defined them as a macros" — Well, don't do that. I recommend updating your question now while you can, before you get any answers. Also, the presentation of your question would be improved by a link to the Wikipedia article on segment trees. \$\endgroup\$ Commented Nov 29, 2020 at 17:33

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.