[core] 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];
            }
      }

---

간단한 코드

update(int n, int v)
{
    int diff = v - tree[n+S] 
    for(n += S;n;n/=2) tree[n]+=diff;
}
int sum(int l, int r)
{
    for(sum=0,l += S,r += S;l<=r;l = (l+1)/2,r = (r-1)/2)
    {
        if (l%2==1) sum+=tree[l];
        if (r%2==0) sum+=tree[r];
return sum;
}
for(int i=S;i>0;i--) tree[i] = tree[2*i]+tree[2*i+1];