Если бы набор был отсортирован, вам не нужно дерево. Самый маленький элемент в диапазоне [i, j] будет иметь индекс i.
Итак, предположим, что элементы вашей последовательности были сохранены в порядке их индексов на листьях дерева. Можете ли вы хранить дополнительную информацию ( ahem , возможно, какое-то минимальное и максимальное значение) в каждом внутреннем узле, чтобы облегчить ваш запрос?
Если это так, то если дерево сбалансировано и если вы можете ответить на ваш запрос, посмотрев только на два пути от корня до двух элементов в {i, j}, то вы достигнете своего O (log N ) стоимость поиска. Поскольку сбалансированное бинарное дерево с N листьями содержит (2N-1) общих узлов, вы также будете удовлетворять пределу O (N) хранения.
ПОДРОБНОЕ ОПИСАНИЕ: рассмотрите возможность вычисления минимального значения в диапазоне [i, j].
В каждом внутреннем узле A дерева сохраняйте минимальное значение для всех листьев под ним. Это может быть вычислено снизу вверх при первом построении дерева.
Теперь начните с листа i. Идите вверх по дереву, сохраняя в качестве минимального значения вашего кандидата значение в i или что-либо, известное как правое от i и левое от j. Остановите один узел ниже общего предка i и j.
Начните снова с листа j. Поднимитесь вверх по дереву, еще раз сохранив в качестве кандидата минимальное значение в j или что-либо, о чем известно, что оно находится слева от j и справа от i.
Ваш минимум для [i, j] равен минимуму двух вычисленных вами значений. Вычисление максимума происходит аналогично. Общее требование к памяти составляет 2 значения для внутреннего узла плюс два указателя для внутреннего узла плюс одно значение для листа, что составляет N + 4 (N-1) для полного дерева.
Путь, по которому вы идете вверх по дереву из листа i, это тот же путь, по которому вы шли бы по дереву, если бы вы искали лист i.
C # КОД ДЛЯ ПОИСКА:
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);
}
}
}
C # КОД ДЛЯ ТЕСТИРОВАНИЯ:
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;
}
}
}