세그먼트 트리 라이브러리 개발(C++) #1

지금까지는 세그먼트 트리 문제 풀 때마다 새로 구현했었는데, 

오늘 엉겁결에 세그먼트 트리 라이브러리를 개발해 보았습니다.

지금까지 사용해 본 C++ STL을 떠올리면서 최대한 비슷하게 만드려 노력했는데

충분히 쓰기 편한지는 모르겠네요ㅠㅠ

구간 쿼리와 점 업데이트를 처리할 수 있고 구간 업데이트는 아직 처리하지 못합니다.

 

멤버 변수

1. T* tree - 세그먼트 트리를 나타낼 배열(을 동적할당할 포인터)입니다. 
2. T* arr - 세그먼트 트리에 저장할 원소들을 담은 배열(을 동적할당할 포인터)입니다.
3. int size, cap - 각각 원래 배열의 크기, 세그먼트 트리 배열의 크기를 나타냅니다.
4. T(*oper)(T, T) - 세그먼트 트리의 리프 노드가 아닌 노드의 값은 두 자식 노드의 값을 덧셈, min/max 연산 등으로 처리한 결과입니다. 이러한 연산을 담는 함수 포인터로, 라이브러리의 활용성을 높이기 위해 넣었습니다.

 

메소드

1. seg_tree() - seg_tree<int> seg; 처럼 먼저 선언할 수 있도록 추가했습니다.
2. seg_tree(int s, T(*fun)(T, T)) - 생성자입니다. 배열의 크기와 함수 포인터를 입력받아 tree, arr에 동적할당하고 oper를 입력받은 함수로 초기화합니다.
3. void init(int now, int l, int r) - 일반적인 세그먼트 트리의 초기화 함수입니다. arr이 모두 차 있을 때 실행되어야 합니다.
4. void init() - 입력 버퍼에서 arr을 모두 입력받고 2. 를 호출합니다.
5. void init(T* s, T* e) - arr으로 사용할 배열의 시작 주소, 끝 다음 주소를 전달받아 해당 구간 - [s, e) - 의 데이터를 arr에 복사한 뒤 2. 를 호출합니다.
6. void update(int now, int l, int r, int idx, T v) - idx번째 원소를 v로 변경하는(update 쿼리를 수행하는) 함수입니다. oper를 활용해 리프 노드가 아닌 노드들의 값을 업데이트합니다. 
7. void update(int idx, T v), void update(long long idx, T v) - update 쿼리를 수행할 때 사용자가 실제로 호출하는 함수입니다. 5. 를 호출하며, idx가 long long 자료형이면 형변환합니다.
8. T quary(int now, int nowl, int nowr, int l, int r) - l부터 r 사이의 원소들에 대한 쿼리를 수행합니다. oper를 활용합니다.
9. T quary(int l, int r), T quary(long long l, long long r) - 6. 과 마찬가지로 구간 쿼리를 수행할 때 사용자가 실제로 호출하는 함수입니다.

코드

 

수정/보완할 점

• vector로도 arr을 초기화할 수 있도록 init함수 추가 - init(v.begin(), v.end()) 형식으로 만들고 싶은데 어떻게 하는지 모르겠어요
• 구간 업데이트 연산도 가능하게 바꾸기 - 구간 업데이트를 할 수 있으면 점 업데이트도 할 수 있긴 한데.. 따로 구현할지 지금 구현에 추가할지 고민중입니다

 

궁금한 점

• 일단 배열을 동적할당해서 쓰고 있으니 소멸자에서 배열의 메모리를 해제해야 할 것 같은데.. 메모리 해제 코드를 넣었더니 Expression: is_block_type_valid(header->_block_use), Expression: _CrtisValidHeapPointer(block) 런타임 에러가 발생합니다. 메모리 해제 코드를 작성하지 않으면 잘 돌아가서 일단 주석 처리해 두었는데 왜 그럴까요??
• seg_tree<int> seg; 처럼 먼저 선언해두고 나중에 2. 를 이용하여 대입하면 소멸자가 호출됩니다. 선언과 동시에 2. 생성자를 이용하면 호출되지 않습니다. 인스턴스에 새로운 인스턴스를 대입할 때는 원래 인스턴스를 소멸시키고 대입하는 것 같은데, 잘은 모르겠지만 생각하지 못한 부분이라 신기해요
  

  

  신기하당