segment Tree

세그먼트 트리는 구간 정보로 사용자가 원하는 아무 값이나 저장해 두는데, 가장 대표적인 사용 예는

• 구간에 속한 원소들의 합
• 구간에 속한 원소들의 곱
• 구간 원소들 중 최댓값
• 구간 원소들 중 최솟값

등의 활용처가 있습니다.

/** * @param L- 구하고자 하는 범위의 좌측 값 * @param R- 구하고자 하는 범위의 우측 값 * @param nodeNum - 현재 위치 (1번은 root이다.처음에는 1번부터...) * @param nodeL - 현재 nodeNum 값의 범위 중 좌측 값 * @param nodeR - 현재 nodeNum 값의 범위 중 우측 값 * @return */ public static int sum(int L, int R, int nodeNum, int nodeL, int nodeR) { //전혀 겹치지 않는다면, 0을 리턴합니다. if (R < nodeL || nodeR < L) return 0; // 완전 포함관계에 있다면, 현재 nodeNum값의 범위의 값을 바로 리턴합니다. if (L <= nodeL && nodeR <= R) return data[nodeNum]; int mid = (nodeL + nodeR) / 2; //좌측과 우측으로 나누어서 재귀적으로 호출합니다. return sum(L, R, nodeNum * 2, nodeL, mid) + sum(L, R, nodeNum * 2 + 1, mid + 1, nodeR); } /** * @param index -갱신하고자하는 위치 * @param val - 갱신하려는 값 */ public static void update(int index, int val) { index += arrayLength; data[index] = val; while (index > 1) { index /= 2; // 이때, 최솟값/ 최대값/ 혹은 합등의 결과를 취사선택하여, 저장하도록 합니다. data[index] = data[index * 2] + data[index * 2 + 1]; }  }