Drzewo segmentów

Poziom trudności Ciężko
Często zadawane pytania Amazonka KodNation Google Microsoft Uber
Zaawansowana struktura danych Drzewo segmentów Drzewoodwiedzajacy 82

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Jeśli wykonujemy dodawanie w danym zakresie szyk których wartości elementów są aktualizowane w dowolnym momencie. Następnie w tego typu problemie radzimy sobie z użyciem segmentu drzewo Struktura. Biorąc pod uwagę tablicę [] z n elementami i musisz odpowiedzieć na wiele zapytań, każde z zapytań jest jednym z dwóch typów:
1. 1 ix: Ustaw a [i] = x
2. 2 lr: Znajdź i wypisz sumę elementów między l i r włącznie

Przykład

wejście:
a [] = {2, 5, 9, 8, 11, 3}
q = 3 (liczba zapytań)
2 3 5
1 2 8
2 0 5

wyjście:
22
37

Naiwnym podejściem do rozwiązania powyższego problemu jest uruchomienie pętli od l do r do i znalezienie sumy zakresu, a do aktualizacji bezpośrednio ustawiamy wartość a [i] jako x.

Podejście i reprezentacja drzewa segmentów

  1. Węzły liści drzewa segmentu to elementy danej tablicy.
  2. Każdy węzeł wewnętrzny przechowuje sumę swoich dzieci.

Drzewo segmentów jest reprezentowane jako tablica w pamięci, jest to pełne drzewo binarne, ponieważ każdy węzeł ma 2 lub 0 dzieci i wszystkie poziomy są wypełnione, z wyjątkiem ostatniego poziomu. Gdy jest reprezentowany jako tablica, istnieją spacje, które nigdy nie były używane, stąd rozmiar drzewa segmentu to (2 * x - 1), gdzie x jest najmniejszą potęgą 2 większą lub równą n.

Drzewo segmentów dla powyższego przykładu jest pokazane na obrazku.

Drzewo segmentówszpilka

Budowa

  1. Najpierw przydzielamy pamięć równą rozmiarowi drzewa segmentu, to znaczy tworzymy tablicę o rozmiarze równym rozmiarowi drzewa segmentu.
  2. Następnie dla każdego węzła wartość tego węzła jest równa sumie jego lewego i prawego dziecka.
  3. Więc piszemy kod rekurencyjny, aby znaleźć wartość każdego węzła,
    wartość [i] = wartość [2 * i + 1] + wartość [2 * i + 2] // Lewe dziecko i to (2 * i + 1), a prawe dziecko to (2 * i + 2)
  4. Podstawowym przypadkiem powtarzania jest sytuacja, w której jest to węzeł liścia, dla węzła liścia wartość węzła jest równa wartości obecnej w tablicy, ponieważ oba jego elementy potomne są zerowe (lub nieobecne).

Aktualizacja elementu (zapytanie typu 1)

Niech i-ty indeks musi zostać zaktualizowany do x, a jego pierwotna wartość wynosiła y, czyli musimy zwiększyć jego wartość o (x - y), a także wszystkie sumy zawierające ten indeks w swoim zakresie również będą musiały zostać zwiększone o (x - y), więc piszemy w tym celu rekurencyjny kod,

  1. Zacznij od korzenia.
  2. Jeśli bieżący węzeł zawiera i w swoim zakresie, zwiększ wartość o (x- y) i powtórz dla swojego lewego i prawego dziecka.
  3. Jeśli aktualny węzeł nie zawiera i w swoim zakresie, to nie wprowadzamy w nim żadnych zmian

Zapytanie o zakres sumy (zapytanie typu 2)

  1. Zacznij od węzła głównego, jeśli zakres węzłów jest między l i r, zwróć wartość tego węzła.
  2. Jeśli zakres węzła jest całkowicie poza zakresem l i r, zwraca 0.
  3. We wszystkich innych przypadkach zwróć sumę odpowiedzi na zapytanie (l, r) dla jego lewego i prawego dziecka.

Kod JAVA dla sumy zakresów przy użyciu drzewa segmentów

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);
            }
        }
    }
}

Kod C ++ dla sumy zakresów przy użyciu drzewa segmentów

#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

Analiza złożoności

Złożoność czasowa dla typ 1 zapytanie to O (1) a dla typ 2 zapytanie, to jest Na), można to zoptymalizować za pomocą drzewa segmentów.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »