Рубрики

GCD заданных диапазонов индексов в массиве

Дан массив a [0. , , н-1]. Мы должны быть в состоянии эффективно найти GCD от индекса qs (начало запроса) до qe (конец запроса), где 0 <= qs <= qe <= n-1.

Пример :

Input : a[] = {2, 3, 60, 90, 50};
        Index Ranges : {1, 3}, {2, 4}, {0, 2}
Output: GCDs of given ranges are 3, 10, 1

Способ 1 (простой)

Простое решение — запустить цикл от qs до qe и найти GCD в заданном диапазоне. Это решение занимает O (n) время в худшем случае.

Метод 2 (2D Array)

Другое решение заключается в создании двумерного массива, в котором запись [i, j] хранит GCD в диапазоне arr [i..j]. GCD заданного диапазона теперь можно рассчитать за время O (1), но предварительная обработка занимает время O (n ^ 2). Кроме того, этот подход требует O (n ^ 2) дополнительного пространства, которое может стать огромным для больших входных массивов.

Метод 3 (Сегментное дерево)

Предпосылки: Набор 1-го сегмента, Набор 2-го сегмента
Сегментное дерево может использоваться для предварительной обработки и запроса в умеренное время. При использовании дерева сегментов время предварительной обработки равно O (n), а время GCD-запроса — O (Logn). Требуется дополнительное пространство O (n) для хранения дерева сегментов.

Представление Сегментных деревьев

  • Конечные узлы являются элементами входного массива.
  • Каждый внутренний узел представляет GCD всех листьев под ним.

Массивное представление дерева используется для представления деревьев сегментов, т. Е. Для каждого узла с индексом i,

  • Левый ребенок по индексу 2 * i + 1
  • Правый ребенок на 2 * i + 2, а родитель на полу ((i-1) / 2).

Построение дерева сегментов из заданного массива

  • Начните с сегмента обр [0. , , п-1] и продолжайте делиться на две половины. Каждый раз, когда мы делим текущий сегмент на две половины (если он еще не стал сегментом длины 1), затем вызываем одну и ту же процедуру для обеих половин, и для каждого такого сегмента мы сохраняем значение GCD в узле дерева сегмента.
  • Все уровни построенного дерева сегментов будут полностью заполнены, кроме последнего уровня. Кроме того, дерево будет полным двоичным деревом (каждый узел имеет 0 или два дочерних элемента), потому что мы всегда делим сегменты на две половины на каждом уровне.
  • Поскольку построенное дерево всегда является полным двоичным деревом с n листьями, будет иметься n-1 внутренних узлов. Таким образом, общее количество узлов будет 2 * n — 1.
  • Высота сегмента дерева будет & lceillog 2 n & rceil. Поскольку дерево представлено с использованием массива, и необходимо поддерживать связь между родительскими и дочерними индексами, объем памяти, выделенной для дерева сегментов, будет 2 * 2 ⌈log 2 n⌉ — 1

Запрос для GCD заданного диапазона

/ qs --> query start index, qe --> query end index
int GCD(node, qs, qe)
{
   if range of node is within qs and qe
      return value in node
   else if range of node is completely 
      outside qs and qe
      return INFINITE
   else
      return GCD( GCD(node's left child, qs, qe), 
                  GCD(node's right child, qs, qe) )
}

Ниже приведена реализация этого метода.

C ++

// C ++ Программа для поиска GCD числа в заданном диапазоне
// используя деревья сегментов
#include <bits/stdc++.h>

using namespace std;

  
// Хранить дерево сегментов

int *st;

  
// Функция для поиска gcd из 2 чисел.

int gcd(int a, int b)

{

    if (a < b)

        swap(a, b);

    if (b==0)

        return a;

    return gcd(b, a%b);

}

  
/ * Рекурсивная функция для получения gcd данного

    диапазон индексов массива. Ниже приведены параметры для

    эта функция.

  

    st -> Указатель на дерево сегментов

    si -> Индекс текущего узла в дереве сегментов. Первоначально

               0 передается как root всегда с индексом 0

    ss & se -> Начальный и конечный индексы сегмента

                 представлен текущим узлом, т. е. st [index]

    qs & qe -> начальные и конечные индексы диапазона запросов * /

int findGcd(int ss, int se, int qs, int qe, int si)

{

    if (ss>qe || se < qs)

        return 0;

    if (qs<=ss && qe>=se)

        return st[si];

    int mid = ss+(se-ss)/2;

    return gcd(findGcd(ss, mid, qs, qe, si*2+1),

               findGcd(mid+1, se, qs, qe, si*2+2));

}

  
// Находим gcd заданного диапазона

int findRangeGcd(int ss, int se, int arr[],int n)

{

    if (ss<0 || se > n-1 || ss>se)

    {

        cout << "Invalid Arguments" << "\n";

        return -1;

    }

    return findGcd(0, n-1, ss, se, 0);

}

  
// Рекурсивная функция, которая создает дерево сегментов для
// массив [ss..se]. si - индекс текущего узла в сегменте
// дерево ул

int constructST(int arr[], int ss, int se, int si)

{

    if (ss==se)

    {

        st[si] = arr[ss];

        return st[si];

    }

    int mid = ss+(se-ss)/2;

    st[si] = gcd(constructST(arr, ss, mid, si*2+1),

                 constructST(arr, mid+1, se, si*2+2));

    return st[si];

}

  
/ * Функция для построения дерева сегментов из заданного массива.

   Эта функция выделяет память для дерева сегментов и

   вызывает constructSTUtil () для заполнения выделенной памяти * /

int *constructSegmentTree(int arr[], int n)

{

   int height = (int)(ceil(log2(n)));

   int size = 2*(int)pow(2, height)-1;

   st = new int[size];

   constructST(arr, 0, n-1, 0);

   return st;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int a[] = {2, 3, 6, 9, 5};

    int n = sizeof(a)/sizeof(a[0]);

  

    // Построить дерево сегментов из заданного массива

    constructSegmentTree(a, n);

  

    // Начальный индекс диапазона. Эти индексы основаны на 0.

    int l = 1;

  

    // Последний индекс диапазона. Эти индексы основаны на 0.

    int r = 3;

    cout << "GCD of the given range is:";

    cout << findRangeGcd(l, r, a, n) << "\n";

  

    return 0;

}

Джава

// Java-программа для поиска GCD числа в заданном диапазоне
// используя деревья сегментов

import java.io.*;

  

public class Main

{

    private static int[] st; // Массив для хранения дерева сегментов

  

    / * Функция для построения дерева сегментов из заданного массива.

       Эта функция выделяет память для дерева сегментов и

       вызывает constructSTUtil () для заполнения выделенной памяти * /

    public static int[] constructSegmentTree(int[] arr)

    {

        int height = (int)Math.ceil(Math.log(arr.length)/Math.log(2));

        int size = 2*(int)Math.pow(2, height)-1;

        st = new int[size];

        constructST(arr, 0, arr.length-1, 0);

        return st;

    }

  

    // Рекурсивная функция, которая создает сегмент

    // Дерево для массива [ss..se]. si - индекс текущего

    // узел в сегментном дереве st

    public static int constructST(int[] arr, int ss,

                                  int se, int si)

    {

        if (ss==se)

        {

            st[si] = arr[ss];

            return st[si];

        }

        int mid = ss+(se-ss)/2;

        st[si] = gcd(constructST(arr, ss, mid, si*2+1),

                     constructST(arr, mid+1, se, si*2+2));

        return st[si];

    }

  

    // Функция для поиска gcd из 2 чисел.

    private static int gcd(int a, int b)

    {

        if (a < b)

        {

            // Если b больше, чем своп a и b

            int temp = b;

            b = a;

            a = temp;

        }

  

        if (b==0)

            return a;

        return gcd(b,a%b);

    }

  

    // Находим gcd заданного диапазона

    public static int findRangeGcd(int ss, int se, int[] arr)

    {

        int n = arr.length;

  

        if (ss<0 || se > n-1 || ss>se)

            throw new IllegalArgumentException("Invalid arguments");

  

        return findGcd(0, n-1, ss, se, 0);

    }

  

    / * Рекурсивная функция для получения gcd данного

    диапазон индексов массива. Ниже приведены параметры для

    эта функция.

  

    st -> Указатель на дерево сегментов

    si -> Индекс текущего узла в дереве сегментов. Первоначально

               0 передается как root всегда с индексом 0

    ss & se -> Начальный и конечный индексы сегмента

                 представлен текущим узлом, т. е. st [si]

    qs & qe -> начальные и конечные индексы диапазона запросов * /

    public static int findGcd(int ss, int se, int qs, int qe, int si)

    {

        if (ss>qe || se < qs)

            return 0;

  

        if (qs<=ss && qe>=se)

            return st[si];

  

        int mid = ss+(se-ss)/2;

  

        return gcd(findGcd(ss, mid, qs, qe, si*2+1),

                   findGcd(mid+1, se, qs, qe, si*2+2));

    }

  

    // Код драйвера

    public static void main(String[] args)throws IOException

    {

        int[] a = {2, 3, 6, 9, 5};

  

        constructSegmentTree(a);

  

        int l = 1; // Начальный индекс диапазона.

        int r = 3; // Последний индекс диапазона.

        System.out.print("GCD of the given range is: ");

        System.out.print(findRangeGcd(l, r, a));

    }

}

C #

// C # Программа для поиска GCD числа в заданном диапазоне
// используя деревья сегментов

using System;

  

class GFG

{

    private static int[] st; // Массив для хранения дерева сегментов

  

    / * Функция для построения дерева сегментов из заданного массива.

    Эта функция выделяет память для дерева сегментов и

    вызывает constructSTUtil () для заполнения выделенной памяти * /

    public static int[] constructSegmentTree(int[] arr)

    {

        int height = (int)Math.Ceiling(Math.Log(arr.Length)/Math.Log(2));

        int size = 2*(int)Math.Pow(2, height) - 1;

        st = new int[size];

        constructST(arr, 0, arr.Length - 1, 0);

        return st;

    }

  

    // Рекурсивная функция, которая создает сегмент

    // Дерево для массива [ss..se]. si - индекс текущего

    // узел в сегментном дереве st

    public static int constructST(int[] arr, int ss,

                                int se, int si)

    {

        if (ss == se)

        {

            st[si] = arr[ss];

            return st[si];

        }

        int mid = ss + (se - ss) / 2;

        st[si] = gcd(constructST(arr, ss, mid, si * 2 + 1),

                    constructST(arr, mid + 1, se, si * 2 + 2));

        return st[si];

    }

  

    // Функция для поиска gcd из 2 чисел.

    private static int gcd(int a, int b)

    {

        if (a < b)

        {

            // Если b больше, чем своп a и b

            int temp = b;

            b = a;

            a = temp;

        }

  

        if (b == 0)

            return a;

        return gcd(b,a % b);

    }

  

    // Находим gcd заданного диапазона

    public static int findRangeGcd(int ss, 

                        int se, int[] arr)

    {

        int n = arr.Length;

  

        if (ss < 0 || se > n-1 || ss > se)

        {

            Console.WriteLine("Invalid arguments");

            return int.MinValue;

        }

  

        return findGcd(0, n - 1, ss, se, 0);

    }

  

    / * Рекурсивная функция для получения gcd данного

    диапазон индексов массива. Ниже приведены параметры для

    эта функция.

  

    st -> Указатель на дерево сегментов

    si -> Индекс текущего узла в дереве сегментов. Первоначально

            0 передается как root всегда с индексом 0

    ss & se -> Начальный и конечный индексы сегмента

                представлен текущим узлом, т. е. st [si]

    qs & qe -> начальные и конечные индексы диапазона запросов * /

    public static int findGcd(int ss, int se, int qs, int qe, int si)

    {

        if (ss > qe || se < qs)

            return 0;

  

        if (qs <= ss && qe >= se)

            return st[si];

  

        int mid = ss + (se - ss)/2;

  

        return gcd(findGcd(ss, mid, qs, qe, si * 2 + 1),

                findGcd(mid + 1, se, qs, qe, si * 2 + 2));

    }

  

    // Код драйвера

    public static void Main(String[] args)

    {

        int[] a = {2, 3, 6, 9, 5};

  

        constructSegmentTree(a);

  

        int l = 1; // Начальный индекс диапазона.

        int r = 3; // Последний индекс диапазона.

        Console.Write("GCD of the given range is: ");

        Console.Write(findRangeGcd(l, r, a));

    }

}

  
// Этот код предоставлен 29AjayKumar


Выход:

 GCD of the given range is: 3

Сложность времени: Сложность времени для построения дерева равна O (n * log (min (a, b))), где n — количество режимов, а a и b — узлы, GCD которых вычисляется во время операции слияния. Всего существует 2n-1 узлов, и значение каждого узла вычисляется только один раз при построении дерева. Временная сложность запроса составляет O (Log n * Log n).

Эта статья предоставлена Nikhil Tekwani . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

GCD заданных диапазонов индексов в массиве

0.00 (0%) 0 votes