느리게 갱신되는 세그먼트 트리 (Lazy Propagation)느리게 갱신되는 세그먼트 트리(Lazy Propagation)는 세그먼트 트리에서 구간 업데이트를 더 효율적으로 처리하기 위해 사용하는 기법이다. 구간의 여러 값을 한 번에 갱신하고, 그 후에 구간에 대한 정보를 빠르게 얻어야 할 때 사용된다. 1. 느리게 갱신되는 세그먼트 트리란?기본 세그먼트 트리는 특정 구간의 값(합, 최대값 등)을 빠르게 쿼리할 수 있게 해준다. 그런데 만약 구간 내 모든 값에 동일한 연산(ex. 더하기)을 여러 번 적용해야 하는 경우, 기본 세그먼트 트리로는 비효율적일 수 있다. 최악의 경우 nlogn의 시간이 걸릴 수 있기 때문이다. 이때 느리게 갱신되는 세그먼트 트리를 사용하면 구간 전체에 대한 업데이트를 지연시..
세그먼트 트리세그먼트 트리는 효율적인 구간 연산을 처리하기 위해 사용되는 트리 구조이다. 주어진 배열에서 특정 구간의 합이나 최대값/최소값 등과 같은 정보를 빠르게 구해야 할 때 유용하다. 이 구조를 사용하면 배열의 값을 업데이트하거나 구간의 값을 구하는 작업을 빠르게 처리할 수 있다. 1. 세그먼트 트리란 무엇인가세그먼트 트리는 주어진 배열을 관리하는 트리 구조로, 배열의 특정 구간에 대한 연산(예: 합, 최대값, 최소값 등)을 효율적으로 처리하는 데 사용된다. 일반적으로 배열의 크기가 커질수록 배열의 구간 합이나 구간 최대/최소를 구하는 시간이 오래 걸리는데, 세그먼트 트리를 사용하면 로그 시간(O(logN)))에 이런 연산을 처리할 수 있다. 즉, 세그먼트 트리는 배열의 구간 정보를 미리 저장해 두..
코드#include #include #include #include #include using namespace std;typedef long long ll;ll tc, n, m, a[1000004],x,y,z,k;void init(vector &tree, int node, int start, int end) { // 리프노드 if(start == end) { tree[node] = a[start]; } else { int mid = (start + end) / 2; init(tree, node*2, start, mid); // 부모 기준 왼쪽 노드 탐색 init(tree, node*2 + 1, mid + 1, end); // 부모 기준 ..
