누적된 변환과 lazy propagation 알고리즘
안녕하세요. 2 ~ 3편에 걸쳐서, 레이지 프로퍼게이션을 적용한 세그먼트 트리를 쓰도록 하겠습니다. 세그먼트 트리에 쓰이는 lazy 기법을 1줄로 요약하면 아래와 같습니다. 네. 앞으로 쓸 2 ~ 3편 글에 대한 핵심입니다. 이것만 정확하게 이해하시면 됩니다. 정말 중요한 키워드는 굵게 강조 표시까지 했는데요. 변환, 흡수, 전파. 이 셋입니다. 변환, 흡수, 전파? 이게 대체 무엇을 의미할까요? 이번 시간에는 이 중에 첫 번째 키워드와 두 번째 키워드인 변환과 흡수에 대해 알아보도록 하겠습니다. 왜 자식에 전파하는지는 다음 포스트에서 이야기 해 보도록 하겠습니다. 1번 변환을 생각해 봅시다. 이 변환을 함수 f(v)로 표현해 봅시다. 그러면, f(v) = v + a가 됩니다. 다음에, 2번 변환을 생각..
자료알고/자료구조
2020. 2. 29. 22:37
최근댓글