Подтвердить что ты не робот

Какую структуру данных, использующую O (n) -хранилище с временем вывода O (log n), следует использовать для минимальных запросов Range?

Меня озадачивает следующий вопрос о домашнем задании для класса алгоритмов:

Предположим, что нам задана последовательность из n значений x 1, x 2... x n и искать быстро отвечать на повторяющиеся запросы form: данные я и j, найдите наименьший значение в x i... x j

Создайте структуру данных, которая использует O (n) пространство и ответы на запросы в O (log n) время.

Во-первых, я не уверен, относится ли последовательность к отсортированному набору или к несортированному множеству, но, поскольку он не говорит об этом, я буду считать, что средства последовательности несортированы.

Итак, я понимаю, что это, очевидно, должно включать двоичное дерево, если мы говорим о времени поиска O (log N). В принципе, я полагаю, у вас есть набор S, и вы вставляете каждый элемент в S в двоичное дерево. Проблема в том, что вопрос в основном требует, чтобы я придумал способ ответа на запросы, где мне задан диапазон индексов в несортированный набор, - и затем определите самое низкое значение в этом диапазоне в O (log N) времени. Как это возможно? Даже если каждый номер набора вставляется в дерево, лучше всего я могу найти любое конкретное число в O (log N) времени. Это не позволяет мне найти наименьшее значение в несортированном диапазоне чисел в S.

Любые предложения?

4b9b3361

ОТВЕТЫ

Ответ 1

Хорошо, я думаю, у меня есть хорошее начало для вас, и я узнал что-то новое в этом процессе.

Я бы взглянул на запись в Википедии Декартовы деревья. Я не собираюсь рассказывать вам больше, потому что боюсь сделать домашнее задание для вас, но вы, кажется, умный парень, поэтому я полагаю, что вы можете это исправить.

Спасибо, что помогли мне изучить новую структуру данных, кстати!

Ответ 2

Если набор был отсортирован, вам не понадобится дерево. Наименьший элемент в диапазоне [i, j] имел бы индекс i.

Итак, предположим, что элементы вашей последовательности были сохранены в порядке их индексов у листьев дерева. Можете ли вы сохранить какую-либо дополнительную информацию (например, возможно, какой-то минимум и максимум) в каждом интерьере node, чтобы облегчить ваш запрос?

Если да, то если дерево сбалансировано, и если вы можете ответить на свой запрос, посмотрев только на два пути от корня до двух элементов в {i, j}, то вы достигнете своего O (log N). Поскольку сбалансированное двоичное дерево с N листьями содержит (2N-1) полные узлы, вы также будете удовлетворять своему пределу хранения O (N).

ПОДРОБНОЕ ОПИСАНИЕ: Рассмотрим вычисление минимального значения в диапазоне [i, j].

В каждом внутреннем дереве node A дерева сохраняйте минимальное значение для всех листьев под ним. Это может быть вычислено снизу вверх, когда дерево сначала построено.

Теперь начните с листа i. Поднимитесь по дереву, сохраняя в качестве вашего кандидата минимальное значение значение в я или все, что известно как справа от i, так и слева от j. Остановите один node ниже взаимного предка я и j.

Начните снова с листа j. Поднимитесь по дереву, снова сохраняя в качестве вашего кандидата минимум значение в j или все, что известно как слева, так и справа от i.

Ваш минимум для [i, j] является минимальным из двух вычисленных значений. Вычисление максимума аналогично. Общая потребность в хранилище - 2 значения на внутреннее пространство node плюс два указателя на внутреннюю часть node плюс одно значение на лист, что равно N + 4 (N-1) для полного дерева.

Путь, по которому вы перемещаетесь по дереву из листа i, - это тот же путь, по которому вы едете по дереву, если будете искать лист i.

С# КОД ДЛЯ ПОИСКА:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace RangeSearch
{
    public class RangeSearch
    {
        int[] tree;
        int N;

        int LeafLocation(int leafNumber) { return leafNumber + N - 1; }
        int LeafValue(int leafNumber) { return tree[ LeafLocation(leafNumber)]; }
        int LeftChild(int x) { return 2*x + 1; }
        int RightChild(int x) { return 2*x + 2; }
        int Parent(int x) { return (x-1)/2; }
        bool IsPowerOf2(int x) { while (x > 0) { if (x == 1) return true; if ((x & 1) == 1 ) return false; x = x >> 1; } return false; }
        bool IsAncestorOf( int x, int y ) { if( x>y ) return false;  return x==y || IsAncestorOf(LeftChild(x), y) || IsAncestorOf(RightChild(x),y); } // note: violating time bound for legibility, can fix by storing min/max descendant index at each node

        public RangeSearch(params int[] vals)
        {
            if (!IsPowerOf2(vals.Length))
                throw new ArgumentException("this implementation restricted to N being power of 2");
            N = vals.Length;
            tree = new int[2 * N - 1];
            // the right half of the array contains the leaves
            vals.CopyTo(tree, N - 1);
            // the left half of the array contains the interior nodes, each of which holds the minimum of all its children
            for (int i = N - 2; i >= 0; i--)
                tree[i] = Math.Min(tree[LeftChild(i)], tree[RightChild(i)]);           
        }

        public int FindMin(int a, int b)
        {
            if( a>b )
                throw new ArgumentException( "FindMin expects a range [a,b] with a<=b" );
            int x = Walk( a, true, b);
            int y = Walk( b, false, a);
            return Math.Min(x, y);
        }

        int Walk( int leafNumber, bool leftSide, int otherLeafNumber )
        {
            int minSoFar =  LeafValue(leafNumber);
            int leafLocation = LeafLocation(leafNumber);
            int otherLeafLocation = LeafLocation(otherLeafNumber);
            int parent = Parent(leafLocation);
            bool cameFromLeft = (leafLocation == LeftChild(parent));
            return Walk2(minSoFar, parent, cameFromLeft, leftSide, otherLeafLocation);
        }
        int Walk2(int minSoFar, int node, bool cameFromLeft, bool leftSide, int otherLeafLocation)
        {
            if (IsAncestorOf(node, otherLeafLocation))
                return minSoFar;
            if (leftSide)
                minSoFar = !cameFromLeft ? minSoFar : Math.Min(minSoFar, tree[RightChild(node)]);
            else
                minSoFar = cameFromLeft ? minSoFar : Math.Min(minSoFar, tree[LeftChild(node)]);
            return Walk2(minSoFar, Parent(node), node == LeftChild(Parent(node)), leftSide, otherLeafLocation);
        }
    }
}

С# CODE TO TEST IT:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace RangeSearch
{
    class Program
    {
        static void Main(string[] args)
        {
            RangeSearch rngA = new RangeSearch(9, 3, 7, 1);
            System.Diagnostics.Trace.Assert(3 == rngA.FindMin(0, 2) );
            System.Diagnostics.Trace.Assert(1 == rngA.FindMin(0, 3));
            System.Diagnostics.Trace.Assert(1 == rngA.FindMin(1, 3));

            RangeSearch rngB = new RangeSearch(1, 7, 3, 9);
            System.Diagnostics.Trace.Assert(3 == rngB.FindMin(1, 3));
            System.Diagnostics.Trace.Assert(1 == rngB.FindMin(0, 3));
            System.Diagnostics.Trace.Assert(1 == rngB.FindMin(0, 2));

            RangeSearch rngC = new RangeSearch(17, 21, 77, 70, 58, 79, 79, 89);
            System.Diagnostics.Trace.Assert(21 == rngC.FindMin(1, 7));

            RangeSearch rngD = new RangeSearch(94, 78, 88, 72, 95, 97, 89, 83);
            System.Diagnostics.Trace.Assert(72 == rngD.FindMin(1, 6));

            RangeSearch rngE = new RangeSearch(0, 66, 6, 43, 34, 34, 63, 49);
            System.Diagnostics.Trace.Assert(34 == rngE.FindMin(3, 4));

            Random rnd = new Random();
            for (int i = 0; i < 1000000; i++)
            {
                int[] tmp = new int[64];
                for (int j = 0; j < tmp.Length; j++)
                    tmp[j] = rnd.Next(0, 100);
                int a = rnd.Next(0, tmp.Length);
                int b = rnd.Next(a, tmp.Length);
                RangeSearch rng = new RangeSearch(tmp);
                System.Diagnostics.Trace.Assert(Min(tmp, a, b) == rng.FindMin(a, b));
            }
        }

        static int Min(int[] ar, int a, int b)
        {
            int x = ar[a];
            for (int i = a + 1; i <= b; i++)
                x = Math.Min(x, ar[i]);
            return x;
        }

    }
}

Ответ 4

Вы считали дерево интервалов?

Глядя на запись в википедии, она, похоже, соответствует тому, что вы просите. http://en.wikipedia.org/wiki/Interval_tree

EDIT:

Да, кажется, что деревья интервалов не подходят для этого сценария...

Ответ 5

Некоторые подталкивания:

Предположим, вы каким-то образом сохранили минимум всех выровненных * подмассивов длиной 1, 2, 4, 8,...? Как немногие из этих минимумов вы можете уйти, глядя на правильный ответ? Как их сохранить, чтобы вы могли эффективно их извлекать?

(* например, store min (x 0... 3)) и min (x 4... x 7), но не min (x 1... x 4))