안녕하세요 [[problem:MORDOR]] 문제를 책에나와있는 RMQ 방법을 사용해 풀다가 질문드립니다.
책에는 구조체로 구현되어있는데, '클래스로 구현해서 풀어볼까?'하는 생각에 아래와 같이 클래스로 구현해서 푸니까 5000ms제한시간에 시간초과가 나오더군요...
그래서 그냥 책예제처럼 구조체로 구현해서 푸니까 348ms가 나왔네요.

어떤 이유때문에 이렇게 차이가 날까요? 클래스는 구조체와 다르게 생성,소멸 과정에서 작동을 많이하나요? 코드를 읽고쓸준 알아도 언어가 내부적으로는 어떻게 동작하는지 잘 몰라서...ㅠ 질문드려봅니다.
아시는분 알려주시면 감사하겠습니다~!!

아래는 RMQ를 클래스로 구현한것입니다.
~~~ c++
#include
#include
#include
#include

#define INF 987654321

int TC,N,Q,a,b;
vector mountain;

class RMQ {
private:
int n;
vector rangeMin;
public:
RMQ(vector arr);
int init(vector arr,int left,int right,int node);
int query(int left,int right,int node,int nodeLeft,int nodeRight);
int query(int left,int right);
};
RMQ::RMQ(vector arr)
{
n=arr.size();
rangeMin.resize(n*4);
init(arr,0,n-1,1);
}
int RMQ::init(vector arr,int left,int right,int node)
{
if(left==right) return rangeMin[node]=arr[left];
int mid=(left+right)/2;
return rangeMin[node]=min(init(arr,left,mid,node*2),init(arr,mid+1,right,node*2+1));
}
int RMQ::query(int left,int right,int node,int nodeLeft,int nodeRight)
{
if(right<nodeLeft || nodeRight<left) return INF;
if(left<=nodeLeft && nodeRight<=right) return rangeMin[node];
int mid=(nodeLeft+nodeRight)/2;
return min(query(left,right,node*2,nodeLeft,mid),query(left,right,node*2+1,mid+1,nodeRight));
}
int RMQ::query(int left,int right){ return query(left,right,1,0,n-1);}

int main() {
scanf("%d",&TC);
while(TC--){
scanf("%d %d",&N,&Q);
mountain.clear();
while(N--){
scanf("%d",&a);
mountain.push_back(a);
}
RMQ rmq_min(mountain);
for(int i=0;i<mountain.size();++i) mountain[i]=-mountain[i];
RMQ rmq_max(mountain);
while(Q--){
scanf("%d %d",&a,&b);
int ret_min=rmq_min.query(a,b);
int ret_max=rmq_max.query(a,b);
cout<<-(ret_min+ret_max)<<endl;
}
}
}
~~~

아래는 책에있는 RMQ를 구조체로 구현한것입니다. 알고스팟 책에있는 소스코드 있는 곳 에서 내려받은 코드의 주석지운겁니다. 보시면 알겠지만 내부코드 동작과정은 큰차이가 없습니다.

#include<cstdio>
#include<cassert>
#include<cstring>
#include<map>
#include<set>
#include<time.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<utility>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
using namespace std;

#define INT_MAX 987654321

int TC,N,Q,a,b;
vector<int> mountain;
struct RMQ {
    int n;
    vector<int> rangeMin;
    RMQ(const vector<int>& array) {
        n = array.size();
        rangeMin.resize(n * 4);
        init(array, 1, 0, n-1);

    }
    int init(const vector<int>& array, int node, int left, int right) {
        if(left == right)
            return rangeMin[node] = array[left];
        int mid = (left + right) / 2;
        return rangeMin[node] = min(init(array, node*2, left, mid),
                                    init(array, node*2+1, mid+1, right));
    }
    int update(int index, int newValue, int node, int nodeLeft, int nodeRight) {
        if(index < nodeLeft || nodeRight < index) return rangeMin[node];
        if(nodeLeft == nodeRight) return rangeMin[node] = newValue;
        int mid = (nodeLeft + nodeRight) / 2;
        return rangeMin[node] = min(update(index, newValue, node*2, nodeLeft, mid),
                update(index, newValue, node*2+1, mid+1, nodeRight));
    }
    int update(int index, int newValue) { return update(index, newValue, 1, 0, n-1); }
    int query(int left, int right, int node, int nodeLeft, int nodeRight) {
        if(right < nodeLeft || nodeRight < left) return INT_MAX;
        if(left <= nodeLeft && nodeRight <= right) return rangeMin[node];
        int mid = (nodeLeft + nodeRight) / 2;
        return min(query(left, right, node*2, nodeLeft, mid),
                   query(left, right, node*2+1, mid+1, nodeRight));
    }
    int query(int left, int right) { return query(left, right, 1, 0, n-1); }
};
int main() {
    scanf("%d",&TC);
    while(TC--){
        scanf("%d %d",&N,&Q);
        mountain.clear();
        while(N--){
            scanf("%d",&a);
            mountain.push_back(a);
        }
        RMQ rmq_min(mountain);
        for(int i=0;i<mountain.size();++i) mountain[i]=-mountain[i];
        RMQ rmq_max(mountain);
        while(Q--){
            scanf("%d %d",&a,&b);
            int ret_min=rmq_min.query(a,b);
            int ret_max=rmq_max.query(a,b);
            cout<<-(ret_min+ret_max)<<endl;
        }
    }
}