세그먼트 트리

난이도 하드
자주 묻는 질문 아마존 코드네이션 구글 Microsoft 동네 짱
고급 데이터 구조 세그먼트 트리 나무조회수 42

주어진 범위에서 더하기를 수행하는 경우 정렬 요소 값이 언제든지 업데이트됩니다. 그런 다음 이러한 유형의 문제에서 세그먼트를 사용하여 처리합니다. 나무 구조. n 개의 요소가있는 배열 a []가 있고 여러 쿼리에 응답해야하는 경우 각 쿼리는 두 가지 유형 중 하나입니다.
1. 1 ix : a [i] = x 설정
2. 2 lr : l과 r 사이에있는 요소의 합을 찾아 인쇄합니다.

입력 :
a [] = {2, 5, 9, 8, 11, 3}
q = 3 (쿼리 수)
+2 3 5 XNUMX
+1 2 8 XNUMX
+2 0 5 XNUMX

출력 :
22
37

위의 문제를 해결하기위한 순진한 접근 방식은 l에서 r까지의 루프를 실행하고 범위의 합을 찾고 업데이트를 위해 a [i]의 값을 x로 직접 설정하는 것입니다.

세그먼트 트리 접근 및 표현

  1. 세그먼트 트리의 리프 노드는 주어진 배열의 요소입니다.
  2. 각 내부 노드는 자식의 합계를 저장합니다.

세그먼트 트리는 메모리의 배열로 표시되며 모든 노드에 2 개 또는 0 개의 자식이 있고 마지막 수준을 제외한 모든 수준이 채워지기 때문에 완전한 이진 트리입니다. 배열로 표시 할 때 사용되지 않은 공간이 있으므로 세그먼트 트리의 크기는 (2 * x – 1)입니다. 여기서 x는 n보다 크거나 같은 2의 가장 작은 제곱입니다.

위의 예에 대한 세그먼트 트리가 이미지에 표시됩니다.

세그먼트 트리

건설

  1. 먼저 세그먼트 트리의 크기와 동일한 메모리를 할당합니다. 즉, 세그먼트 트리의 크기와 동일한 크기의 배열을 만듭니다.
  2. 그런 다음 모든 노드에 대해이 노드의 값은 왼쪽 및 오른쪽 자식의 합과 같습니다.
  3. 따라서 각 노드의 값을 찾기 위해 재귀 코드를 작성합니다.
    value [i] = value [2 * i + 1] + value [2 * i + 2] // i의 왼쪽 자식은 (2 * i + 1)이고 오른쪽 자식은 (2 * i + 2)
  4. 반복의 기본 사례는 리프 노드 일 때입니다. 리프 노드의 경우 노드의 값은 두 자식이 모두 null (또는 부재)이기 때문에 배열에있는 값과 동일합니다.

요소 업데이트 (Type-1 Query)

i 번째 인덱스를 x로 업데이트하고 원래 값을 y로 설정합니다. 즉, 값을 (x – y)만큼 증가시켜야하며 해당 범위에이 인덱스를 포함하는 모든 합계도 다음만큼 증가해야합니다. (x – y),이를 위해 재귀 코드를 작성합니다.

  1. 루트에서 시작하십시오.
  2. 현재 노드가 범위 내에 i를 포함하면 값을 (x-y)만큼 증가시키고 왼쪽과 오른쪽 자식에 대해 반복합니다.
  3. 현재 노드의 범위 내에 i가 포함되어 있지 않으면 변경하지 않습니다.

합계 범위 쿼리 (유형 -2 쿼리)

  1. 노드 범위가 l과 r 사이이면 루트 노드에서 시작하여이 노드의 값을 반환합니다.
  2. 노드의 범위가 l 및 r 범위를 완전히 벗어나면 0을 반환합니다.
  3. 다른 모든 경우에는 왼쪽 자식이고 오른쪽 자식 인 쿼리 (l, r)의 답변 합계를 반환합니다.

세그먼트 트리를 사용한 범위 합계에 대한 JAVA 코드

public class SegmentTree {
    // Function to find the sum of given range in the segment tree
    // tree[] --> Segment Tree
    // s --> Starting index of segment tree
    // e --> Ending index of segment tree
    // i --> Current index of segment tree
    // l --> Lower index of range
    // r --> Higher index of range
    private static int rangeSum(int tree[], int s, int e, int l, int r, int i) {
        // If the current node range is within the range l and r, return its value
        if (l <= s && r >= e)
            return tree[i];

        // If current node's range is completely outside the range l and r, return 0
        if (e < l || s > r)
            return 0;

        // For all other cases return sum of answers to query for left and right child
        // Left child index = 2 * i + 1
        // Right child index = 2 * i + 2
        int mid = (s + e) / 2;
        return rangeSum(tree, s, mid, l, r, 2 * i + 1) +
                rangeSum(tree, mid + 1, e, l, r, 2 * i + 2);
    }

    // Function to update the segment tree for a given index
    // s --> Starting index of segment tree
    // e --> Ending index of segment tree
    // index --> Index to be changed in the original array
    // diff --> This is to be added in the nodes that contains index in their range
    // i --> Current index of Segment tree
    private static void updateValue(int tree[], int s, int e, int index, int diff, int i) {
        // If the current node does not contain index in its range, make no changes
        if (index < s || index > e)
            return;

        // Current node contains the index in its range, update the current nodes and its children
        // Left child index = 2 * i + 1
        // Right child index = 2 * i + 2
        tree[i] = tree[i] + diff;
        if (s != e) {
            int mid = (s + e) / 2;
            updateValue(tree, s, mid, index, diff, 2 * i + 1);
            updateValue(tree, mid + 1, e, index, diff, 2 * i + 2);
        }
    }

    // A function to create the segment tree recursively between s and e
    // i --> Index of current node in the segment tree
    private static int constructSegmentTree(int tree[], int a[], int s, int e, int i) {
        // Leaf node case
        if (s == e) {
            tree[i] = a[s];
            return a[s];
        }

        // For all other nodes its value is sum of left and right child's value
        // Left child index = 2 * i + 1
        // Right child index = 2 * i + 2
        int mid = (s + e) / 2;
        tree[i] = constructSegmentTree(tree, a, s, mid, i * 2 + 1) +
                constructSegmentTree(tree, a, mid + 1, e, i * 2 + 2);
        // Return the value of current node
        return tree[i];
    }

    // Driver function for segment tree approach
    public static void main(String args[]) {
        int a[] = {2, 5, 9, 8, 11, 3};
        int n = a.length;

        // Calculate the size of the segment tree
        int x = (int) (Math.ceil(Math.log(n) / Math.log(2)));
        int size = 2 * (int) Math.pow(2, x) - 1;

        // Allocate memory for segment tree
        int tree[] = new int[size];

        // Construct the segment tree
        constructSegmentTree(tree, a, 0, n - 1, 0);

        // Queries
        int q = 3;
        int type[] = {2, 1, 2};     // Stores the type of query to process
        int l[] = {3, 2, 0};        // Stores the index of element to be updated for type-1 query and lower range for type-2 query
        int r[] = {5, 8, 5};        // Stores the new value of element for type-1 query and higher range for type-2 query
        for (int j = 0; j < q; j++) {
            if (type[j] == 1) {
                // Type-1 query (Update the value of specified index)
                int index = l[j];
                int value = r[j];
                int diff = value - a[index];            // This diff is to be added to all the range that contains the index

                // Update the value in array a
                a[index] = value;

                // Update segment tree
                updateValue(tree, 0, n - 1, index, diff, 0);
            } else {
                // Type-2 query (Find the Sum of given range)
                int sum = rangeSum(tree, 0, n - 1, l[j], r[j], 0);
                System.out.println(sum);
            }
        }
    }
}

세그먼트 트리를 사용하는 범위 합계에 대한 C ++ 코드

#include <bits/stdc++.h> 
using namespace std; 

// Function to find the sum of given range in the segment tree
// tree[] --> Segment Tree
// s --> Starting index of segment tree
// e --> Ending index of segment tree
// i --> Current index of segment tree
// l --> Lower index of range
// r --> Higher index of range
int rangeSum(int *tree, int s, int e, int l, int r, int i) {
  // If the current node range is within the range l and r, return its value
    if (l <= s && r >= e)
        return tree[i];

    // If current node's range is completely outside the range l and r, return 0
    if (e < l || s > r)
        return 0;
    
  // For all other cases return sum of answers to query for left and right child
    // Left child index = 2 * i + 1
    // Right child index = 2 * i + 2
    int mid = (s + e) / 2;
    return rangeSum(tree, s, mid, l, r, 2 * i + 1) +
                rangeSum(tree, mid + 1, e, l, r, 2 * i + 2);
}

// Function to update the segment tree for a given index
// s --> Starting index of segment tree
// e --> Ending index of segment tree
// index --> Index to be changed in the original array
// diff --> This is to be added in the nodes that contains index in their range
// i --> Current index of Segment tree
void updateValue(int *tree, int s, int e, int index, int diff, int i) {
    // If the current node does not contain index in its range, make no changes
    if (index < s || index > e)
        return;

    // Current node contains the index in its range, update the current nodes and its children
    // Left child index = 2 * i + 1
    // Right child index = 2 * i + 2
    tree[i] = tree[i] + diff;
    if (s != e) {
        int mid = (s + e) / 2;
        updateValue(tree, s, mid, index, diff, 2 * i + 1);
        updateValue(tree, mid + 1, e, index, diff, 2 * i + 2);
    }
}

// A function to create the segment tree recursively between s and e
// i --> Index of current node in the segment tree
int constructSegmentTree(int *tree, int *a, int s, int e, int i) {
    // Leaf node case
    if (s == e) {
        tree[i] = a[s];
        return a[s];
    }

    // For all other nodes its value is sum of left and right child's value
    // Left child index = 2 * i + 1
    // Right child index = 2 * i + 2
    int mid = (s + e) / 2;
    tree[i] = constructSegmentTree(tree, a, s, mid, i * 2 + 1) +
                constructSegmentTree(tree, a, mid + 1, e, i * 2 + 2);
    // Return the value of current node
    return tree[i];
}

// Driver function for segment tree approach  
int main() {
  int a[] = {2, 5, 9, 8, 11, 3};
  int n = sizeof(a)/sizeof(a[0]);
  
  // Calculate the size of the segment tree
  int x = (int)(ceil(log2(n)));  
    int size = 2*(int)pow(2, x) - 1;
  
  // Allocate memory for segment tree
  int tree[size];
  
  // Construct the segment tree
  constructSegmentTree(tree, a, 0, n - 1, 0);
  
  // Queries
    int q = 3;
    int type[] = {2, 1, 2};     // Stores the type of query to process
    int l[] = {3, 2, 0};        // Stores the index of element to be updated for type-1 query and lower range for type-2 query
    int r[] = {5, 8, 5};        // Stores the new value of element for type-1 query and higher range for type-2 query
    for (int j = 0; j < q; j++) {
        if (type[j] == 1) {
            // Type-1 query (Update the value of specified index)
            int index = l[j];
            int value = r[j];
            int diff = value - a[index];            // This diff is to be added to all the range that contains the index

            // Update the value in array a
            a[index] = value;

            // Update segment tree
            updateValue(tree, 0, n - 1, index, diff, 0);
        } else {
            // Type-2 query (Find the Sum of given range)
            int sum = rangeSum(tree, 0, n - 1, l[j], r[j], 0);
            cout<<sum<<endl;
        }
    }
  return 0;
}
22
37

복잡성 분석

시간 복잡성 타입 -1 쿼리는 O (1) 과의 타입 -2 쿼리, 그것은 O (N), 이것은 세그먼트 트리를 사용하여 최적화 할 수 있습니다.

참조

Translate »