반환 자체도 O(n)이긴 한데, 내부에서 이터레이팅을 돌면서 벡터에 값을 채우는 반복문이 있다면 여기서 벌써 O(n) 아닌가요?

C++11 이전에서는 깊은 복사를 수행하기 때문에 O(N)이지만

C++11 부터는 얕은 복사를 통해 O(1)로 이루어집니다.

자세한 내용은 move semantics를 살펴보시면 될 것 같네요. 

@portableangel 질문을 잘못한것같네요 ㅎㅎ 

제가 세그트리를 구현하는데 각각의 노드가 벡터를 가지고 있어야해서 init 함수가 vector<int> 를 반환하도록 했는데

벡터의 반환이 오래걸려봐야 O(n) 이기때문에 아무리 구간트리의 조상 노드가 가지고있는 벡터의 길이(?)가 길어져도(100만 이하) 크게 속도에 미치는 영향이 없나요?반환반환할때마다 lon(n) 이 걸리는데 반환을 최대2n 번 정도하니까 (?) (1+...+n/4+n/2+n)  속도에 혹시라도 영향을 끼칠까봐서요.. 

@yukariko 와 어떻게 그런것까지.. 대단하십니다! 감사합니다