Hello, Freakin world!

www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 전형적인 구간 트리 문제. 구간 트리를 초기화하는 과정에서 중복되는 과정들이 많아 BiFunction을 이용해 함수를 전달받게 만들어 봤는데, 역시 느리다. 가끔씩 문제들을 풀어오면서 느끼고 있었는데, 자바 Stream, 람다의 경우 연산량이 많이지는 경우 for문에 비해 엄청나게 느리다. 속도가 몇 초씩 차이가 날때가 있기 때문에, PS에서는 조심해서 사용할 것. impo..

https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄�� www.acmicpc.net 구간 트리의 개념과 기분 구현을 할 수 있는지 묻는 문제입니다. 구간 트리에 대한 설명은 아래 글을 참고하세용 javachoi.tistory.com/292 구간 트리(Segment Tree) 구간 트리란? 구간 트리의 정체는 이진 트리입니다. 구간 트리 라는 이름은 그저 특정 용도로 사용되는 이진 트리의 한 형태를 나타낼 뿐입니다. 대..

구간 트리란? 구간 트리의 정체는 이진 트리입니다. 구간 트리 라는 이름은 그저 특정 용도로 사용되는 이진 트리의 한 형태를 나타낼 뿐입니다. 대게 구간 트리는 일차원 배열 상의 특정 구간에 대한 요청에 빠르게 대답하기 위해 사용합니다. 예를 들어, 1 2 3 4 5 라는 숫자 배열이 있다고 하겠습니다. 이 배열의 특정 구간의 합을 구한다고 할 때, 가장 간단한 방법은 그 특정 구간을 순회하면서 값을 더해나가는 겁니다. 이 경우 시간 복잡도는 O(n)이 됩니다. 만약 배열의 길이가 10억쯤 된다면 어떨까요? 컴퓨터가 1초에 1억번 정도의 루프를 돌린다고 하면 10초가 걸리겠네요. 그리고 또 이 합연산이 여러번 호출될 가능성이 있다면 어떨까요? 이 연산은 매번 합을 새로 구하기 때문에 문제가 됩니다. 구간..