컴공6 [PS를 위한 자료구조 5강] 세그먼트 트리의 구현(비재귀) PS를 위한 자료구조 1-5강 # 비재귀 세그먼트 트리의 구현 # 에 대해 알아보겠습니다. 지금까지 세그먼트 트리를 모두 재귀 방식으로 구현해왔습니다. 하지만 재귀 호출를 사용하지 않고 세그먼트 트리를 구현할 수 있다니, 믿겨지십니까? 재귀 세그먼트 트리는 비교적 직관적이고 이해가 쉽지만, 비재귀 세그먼트 트리는 이해하기 어렵고 비트연산을 많이 사용해아합니다. 그럼에도 불구하고 왜 비재귀 세그먼트 트리를 사용할까요? 1. 구현이 짧습니다. 2. 동일한 알고리즘 수행의 경우, 함수호출의 횟수가 적은 비재귀가 더 빠릅니다. 3. 그것이 낭만이니까. 웬만해서는 어렵다는 말은 잘 하지 않지만 이번만큼은 조금 어려울 수 있습니다. 그럼 설명을 시작해보겠습니다. 재귀 세그먼트 트리에서는 항상 루트.. 2022. 3. 24. [PS를 위한 자료구조 4강] 게으른 세그먼트 트리의 구현 PS를 위한 컴퓨터 자료구조 강의 1-4강 # 게으른 세그먼트 트리의 구현 # 에 대해 알아보겠습니다. 제목을 보고 드셨을 생각이 뭔지. 잘 압니다. 자료구조가 게으르다고? 뭐지? 저도 똑같은 생각을 했었습니다. 게으른 세그먼트 트리. Lazy Segment Tree에 대해 말씀드리겠습니다. 여기까지 오신 분들은 모두 앞선 연습문제를 풀고 오셨으리라 생각합니다. 아래의 문제를 읽고 오시기 바랍니다. [구간 합 구하기 - 이전 연습문제] https://www.acmicpc.net/problem/2042 [구간 합 구하기 2] https://www.acmicpc.net/problem/10999 무슨 차이가 있는지 느끼셨나요?? 넵, 바로 업데이트 함수가 바뀌었습니다. "idx번 원.. 2022. 3. 24. 이전 1 2 다음
