Euler tour+segment tree
Intuition\nEuler tour+segment tree\n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time complexity:\nO(nlog(n))\n\n- Space co
# Intuition\nEuler tour+segment tree\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\nO(n*log(n))\n\n- Space complexity:\nO(4*n)\n\n# Code\n```\nstruct SegmentTree{\n    int n;\n    vector<int> tree;\n    SegmentTree(int sz){\n        n = 1;\n        while(n < sz){\n            n <<= 1;\n        }\n        tree.assign(2 * n, 0);\n    }\n    void set(int ind, int val){\n        ind += n;\n        tree[ind] = val;\n        ind >>= 1;\n        while(ind > 0){\n            tree[ind] = min(tree[2 * ind], tree[2 * ind + 1]);\n            ind >>= 1;\n        }\n    }\n    int get(int x){\n        // return the first index i, such that s[i] < x\n        int node = 1;\n        while(node < n){\n            int left = (node << 1);\n            int right = (node << 1) + 1;\n            if(tree[left] < x){\n                node = left;\n            }else{\n                node = right;\n            }\n        }\n        return (node - n);\n    }\n};\n\nvector<int> solve(vector<int> &a, vector<pair<int, int>> _queries){\n    int n=a.size();\n    for(int i=1;i<a.size();i++){\n        a[i]--;\n    }\n    int q=_queries.size();\n    vector<vector<pair<int, int>>> queries(n + 1);\n    for(int i = 0; i < q; ++i){\n        int l=_queries[i].first;\n        int r=_queries[i].second;\n        queries[r].push_back({l, i});\n    }\n\n    vector<int> res(q);\n\n    SegmentTree s(100001);\n    for(int i = 1; i <n; ++i){\n        s.set(a[i], i);\n        \n\n        for(auto [l, ind] : queries[i]){\n            res[ind] = s.get(l)+1;\n        }\n    }\n\n    return res;\n}\nclass Solution {\npublic:\n    \n\n    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {\n        int n=parents.size();\n        vector<vector<int>> tree(n);\n        for(int i=1;i<n;i++){\n            tree[parents[i]].push_back(i);\n        }\n        vector<int> euler_tour = {0};\n        vector<int> first_pos(n);\n        vector<int> second_pos(n);\n        function<void(int)> dfs=[&](int u){\n            euler_tour.push_back(nums[u]);\n            first_pos[u]=euler_tour.size()-1;\n            for(int v : tree[u]){\n                dfs(v);\n            }\n            second_pos[u]=euler_tour.size()-1;\n        };\n        dfs(0);\n        vector<pair<int, int>> queries;\n        for(int i=0;i<n;i++){\n            queries.push_back({first_pos[i], second_pos[i]});\n        }\n        \n        return solve(euler_tour, queries);\n    }\n};\n```
['Segment Tree', 'C++']