સેગમેન્ટ ટ્રી  


મુશ્કેલી સ્તર હાર્ડ
વારંવાર પૂછવામાં આવે છે એમેઝોન કોડનેશન Google માઈક્રોસોફ્ટ ઉબેર
અદ્યતન ડેટા સ્ટ્રક્ચર સેગમેન્ટ-ટ્રી વૃક્ષ

જો આપેલ શ્રેણીમાં આપણી પાસે અગત્યનું પ્રદર્શન છે એરે જેના તત્વ મૂલ્યો કોઈપણ સમયે અપડેટ થાય છે. પછી તે પ્રકારની સમસ્યામાં, અમે સેગમેન્ટનો ઉપયોગ કરીને હેન્ડલ કરીએ છીએ વૃક્ષ માળખું. N તત્વો સાથે એરે [a] આપેલ છે અને તમારે બહુવિધ ક્વેરીઝનો જવાબ આપવો પડશે, દરેક ક્વેરી બે પ્રકારના હોય છે:
1. 1 ix: એક [i] = x સેટ કરો
2. 2 એલઆર: એલ અને આર બંનેના સમાવેશ સહિતના ઘટકોનો સરવાળો શોધો અને છાપો

ઉદાહરણ  

ઇનપુટ:
a [] = {2, 5, 9, 8, 11, 3
q = 3 (પ્રશ્નોની સંખ્યા)
2 3 5
1 2 8
2 0 5

આઉટપુટ:
22
37

ઉપરોક્ત સમસ્યાને હલ કરવા માટે નિષ્ક્રીય અભિગમ એ એલ થી આર સુધીની લૂપ ચલાવવી અને શ્રેણીનો સરવાળો શોધવા અને અપડેટ કરવા માટે, અમે સીધા [i] ની કિંમત x તરીકે સેટ કરી.

સેગમેન્ટ ટ્રી અભિગમ અને પ્રતિનિધિત્વ  

  1. સેગમેન્ટ ટ્રીના પાંદડા ગાંઠો આપેલ એરેના ઘટકો છે.
  2. દરેક આંતરિક નોડ તેના બાળકોનો સરવાળો સંગ્રહ કરે છે.

સેગમેન્ટ ટ્રી મેમરીમાં એરે તરીકે રજૂ થાય છે, તે એક સંપૂર્ણ બાઈનરી વૃક્ષ છે કારણ કે દરેક નોડમાં 2 અથવા 0 બાળકો હોય છે અને સંભવતibly છેલ્લા સ્તર સિવાય તમામ સ્તરો ભરાય છે. જ્યારે એરે તરીકે રજૂ થાય છે ત્યારે કેટલીક જગ્યાઓ હોય છે જેનો ક્યારેય ઉપયોગ કરવામાં આવતો નથી, તેથી સેગમેન્ટના ઝાડનું કદ (2 * x - 1) છે, જ્યાં x એ 2 કરતા નાની મોટી અથવા n ની બરાબર શક્તિ છે.

ઉપરોક્ત ઉદાહરણ માટે સેગમેન્ટ ટ્રી છબીમાં બતાવવામાં આવી છે.

આ પણ જુઓ
દ્વિસંગી વૃક્ષ બીએસટી છે કે નહીં તે તપાસવાનો કાર્યક્રમ

સેગમેન્ટ ટ્રી

બાંધકામ  

  1. આપણે પહેલા સેગમેન્ટ ટ્રીના કદની બરાબર મેમરી ફાળવીએ છીએ, એટલે કે, એક એરેજ બનાવો, જે સેગમેન્ટ ટ્રીના કદની બરાબર છે.
  2. પછી, દરેક નોડ માટે, આ નોડનું મૂલ્ય તેના ડાબા અને જમણા બાળકના સરવાળા જેટલું છે.
  3. તેથી, અમે દરેક નોડની કિંમત શોધવા માટે એક રિકર્સીવ કોડ લખીએ છીએ,
    મૂલ્ય [i] = value [2 * i + 1] + મૂલ્ય [2 * i + 2] // મારા ડાબા સંતાન (2 * i + 1) અને જમણા બાળક (2 * i + 2) છે
  4. પુનરાવર્તનનો આધાર કેસ જ્યારે તે પાંદડા નોડ હોય છે, જ્યારે પર્ણ નોડ માટે નોડનું મૂલ્ય એરેમાં હાજર મૂલ્યની બરાબર હોય છે કારણ કે તેના બંને બાળક નલ (અથવા ગેરહાજર) છે.

તત્વને અપડેટ કરવું (પ્રકાર -1 ક્વેરી)  

ચાલો ith ઈન્ડેક્સને x માં અપડેટ કરવું જોઈએ અને તેનું મૂળ મૂલ્ય y હતું, એટલે કે આપણે તેનું મૂલ્ય (x - y) દ્વારા વધારવું પડશે, અને તેમની શ્રેણીમાં આ અનુક્રમણિકા ધરાવતા તમામ રકમ પણ વધારવી પડશે (x - y), તેથી અમે તે કરવા માટે એક રિકર્સીવ કોડ લખીએ છીએ,

  1. મૂળથી પ્રારંભ કરો.
  2. જો વર્તમાન નોડમાં તેની રેન્જની અંદર i હોય, તો પછી (x- y) દ્વારા મૂલ્યમાં વધારો અને તેના ડાબા અને જમણા બાળક માટે ફરીથી આવર્તન.
  3. જો વર્તમાન નોડમાં તેની રેન્જમાં હું શામેલ નથી, તો અમે તેમાં કોઈ ફેરફાર કરીશું નહીં

સરવાળા શ્રેણી ક્વેરી (પ્રકાર -2 ક્વેરી)  

  1. રૂટ નોડથી પ્રારંભ કરો, જો નોડ રેન્જ l અને r ની વચ્ચે હોય તો આ નોડની કિંમત પરત કરો.
  2. જો નોડની રેન્જ l અને r ની શ્રેણીની બહારની છે, તો 0 પરત ફરો.
  3. અન્ય તમામ કિસ્સાઓમાં ક્વેરી (એલ, આર) ના જવાબોની રકમ તેના ડાબા બાળક માટે આપે છે અને તે એક સાચો બાળક છે.
આ પણ જુઓ
ઇન્ફિક્સ રૂપાંતર પર પોસ્ટફિક્સ

સેગમેન્ટ ટ્રીનો ઉપયોગ કરીને શ્રેણી રકમ માટે જાવા કોડ  

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

સેગમેન્ટ ટ્રીનો ઉપયોગ કરીને શ્રેણી રકમ માટે સી ++ કોડ  

#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 ક્વેરી છે ઓ (1) અને માટે પ્રકાર-2 ક્વેરી, તે છે ઓ (એન), સેગમેન્ટ ટ્રીના ઉપયોગ દ્વારા આને optimપ્ટિમાઇઝ કરી શકાય છે.

આ પણ જુઓ
મોરિસ ઇનોર્ડર ટ્રાવર્સલ

સંદર્ભ