4luv1015

일반화 세그먼트 트리 구현 - 3. 업데이트와 쿼리 구현 일반화 세그먼트 트리 구현 - 2. 초기화와 생성자 구현 일반화 세그먼트 트리 구현 - 1. 일반화 프로그래밍이란? 평소와 다름없이 stl로 알고리즘 문제를 풀다가 문득 궁금증이 생겼다. stl은 queue, v 4luv1015.tistory.com 저번 글에서 완성한 세그먼트 트리 하나로 원래라면 전혀 다른 종류의 세그먼트 트리를 구현해야했던 2가지 문제를 아주 간단히 풀어보겠다. 1. 구간 합 세그먼트 트리 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다..

일반화 세그먼트 트리 구현 - 2. 초기화와 생성자 구현 일반화 세그먼트 트리 구현 - 1. 일반화 프로그래밍이란? 평소와 다름없이 stl로 알고리즘 문제를 풀다가 문득 궁금증이 생겼다. stl은 queue, vector 등등과 같이 어떤 자료형이든 사용할 수 있게 일 4luv1015.tistory.com 저번 글에 이어서 이번에는 세그먼트 트리의 업데이트와 쿼리 부분을 구현하여 세그먼트 트리를 완성해보았다. 1. 업데이트 업데이트의 구현의 기본적으로 트리 초기화와 크게 다르지 않다. 다만 특정 값을 더하거나 곱한다던지 아니면 아예 다른 값으로 대체한다던지 업데이트의 방식이 그때그때 다르므로 업데이트하는 방식 또한 함수 포인터로 받도록 했다. void update(int idx,vector val,T (..

일반화 세그먼트 트리 구현 - 1. 일반화 프로그래밍이란? 평소와 다름없이 stl로 알고리즘 문제를 풀다가 문득 궁금증이 생겼다. stl은 queue, vector 등등과 같이 어떤 자료형이든 사용할 수 있게 일반화되 있는데 어떻게 이런 것이 가능할까? 언뜻 보기에 4luv1015.tistory.com 저번 글에 이어서 이번에는 세그먼트 트리의 생성자와 초기화 부분을 구현해보았다. 1. 멤버 변수 세그먼트 트리의 구조체를 만든다면 필요한 멤버 변수가 뭐가 있을지 생각해보았다. ① 트리로 사용할 vector ② 쿼리를 처리하기 위해 필요한 원본 배열의 시작점과 끝점의 index ③ 두 구간의 값을 합할 때 사용할 함수의 포인터 따라서 아래와 같이 구조체를 만들어 주었다. template struct seg..

평소와 다름없이 stl로 알고리즘 문제를 풀다가 문득 궁금증이 생겼다. stl은 queue, vector 등등과 같이 어떤 자료형이든 사용할 수 있게 일반화되어 있는데 어떻게 이런 것이 가능할까? 언뜻 보기에 자바의 제네릭과 같은 기능을 하고 있었기에 찾아보니 c++에도 제네릭과 비슷한 template라는 것이 존재했다. 아래는 template의 구조체와 함수 각각에서의 사용 예시이다. #include using namespace std; template struct s { T val; }; //구조체에서의 사용 template T mySum(T a,T b) { return a+b; } // 함수에서의 사용 int main() { s s1={3}; cout