ベタな実装

数値配列の部分範囲内の最大値は以下のように検索できます。

線形最大値検索

function findMax(nums, start, end, minValue = -Infinity) {
  let maxValue = minValue;
  for (let i = start; i < end; i++) {
    maxValue = Math.max(maxValue, nums[i]);
  }
  return maxValue;
}

ただしこの方法では、一度の検索が線形時間であるため、数万要素数ある配列の場合、何度も範囲を変えながら最大値を求めるような場合には、とても大きな時間がかかってしまいます(繰り返したときの計算量はO(N^2))。

二分木による実装

そこで、これを回避するには、最大値を収めた二分木を一度作成することによって、対数時間で検索できるようになります(繰り返したときの計算量はO(NlogN))。

対数最大値検索

function createMaxTree(nums, start = 0, end = nums.length) {
  const length = end - start;
  if (length === 1) return {max: nums[start], start, end};
  const mid = start + (length >> 1);
  const left = createMaxTree(nums, start, mid);
  const right = createMaxTree(nums, mid, end);
  // [start, end)範囲での最大値がmax
  return {max: Math.max(left.max, right.max), start, end, left, right};
}

function findMax(tree, start, end, minValue = -Infinity) {
  if (end <= tree.start || tree.end <= start) return minValue; // ノードの範囲が完全に範囲外
  if (start <= tree.start && tree.end <= end) return tree.max; // ノードの範囲が完全に範囲内
  // 部分的に範囲内
  const left = findMax(tree.left, start, end, minValue);   
  const right = findMax(tree.right, start, end, minValue); 
  return Math.max(left, right);
}

// 値の更新
function updateMax(tree, i, value) {
  if (i < tree.start || tree.end <= i) return tree.max; // iが完全に範囲外
  const length = tree.end - tree.start;
  if (length === 1) return tree.max = value;
  const left = updateMax(tree.left, i, value);
  const right = updateMax(tree.right, i, value);
  return tree.max = Math.max(left, right);
}

これは"Segment Tree"の非配列での実装例となるようです。

https://cp-algorithms.com/data_structures/segment_tree.html

ほかの例としては、最小値、負値も含む総和、なども可能なよう。

配列上の二分木による実装

配列上の二分木

function createMaxArray(
  nums, start = 0, end = nums.length,
  array = new Array((1 << (Math.ceil(Math.log2(nums.length)) + 1)) - 1), i = 0) {
  const length = end - start;
  if (length === 1) {
    array[i] = nums[start];
    return array;
  }
  const mid = start + (length >> 1);
  const leftI = i * 2 + 1, rightI = leftI + 1;
  createMaxArray(nums, start, mid, array, leftI);
  createMaxArray(nums, mid, end, array, rightI);
  array[i] = Math.max(array[leftI], array[rightI]);
  return array;
}

function findMax(array, nStart, nEnd, start, end, minValue = -Infinity, i = 0) {
  if (end <= nStart || nEnd <= start) return minValue; // ノードの範囲が完全に範囲外
  if (start <= nStart && nEnd <= end) return array[i]; // ノードの範囲が完全に範囲内
  // 部分的に範囲内
  const mid = nStart + ((nEnd - nStart) >> 1);
  const leftI = i * 2 + 1, rightI = leftI + 1;
  const left = findMax(array, nStart, mid, start, end, minValue, leftI);
  const right = findMax(array, mid, nEnd, start, end, minValue, rightI);
  return Math.max(left, right);
}

function updateMaxArray(array, nStart, nEnd, i, value, j = 0) {
  if (i < nStart || nEnd <= i) return array[j]; // iが完全に範囲外
  const length = nEnd - nStart;
  if (length === 1) return array[j] = value;
  const mid = nStart + (length >> 1);
  const leftJ = j * 2 + 1, rightJ = leftJ + 1;
  const left = updateMaxArray(array, nStart, mid, i, value, leftJ);
  const right = updateMaxArray(array, mid, nEnd, i, value, rightJ);
  return array[j] = Math.max(left, right);
}

配列の先頭に全範囲の最大値、次に前半分の最大値、その次に後半分の最大値、という配列になります。

要素数によっては、空白のセルも二分木配列の途中に存在し、たとえば要素数3の場合では、[全体の最大値, 要素0の値, 要素1と2の最大値, 空白, 空白, 要素1の値, 要素2の値]になります。

値配列の要素数3の場合、二分木配列の要素数は7であり、要素数nの値配列に対し、2^(ceil(log2(n))+1)-1要素数の二分木配列ができます。
最悪は、値配列の要素数2^n+1の場合で、最後2つが埋まり、その前に空白が2^ceil(log2(n))-2個続くことになります。

手法は二分木構造体と全く同じですが、配列上に二分木を作る場合、検索時に元の値配列のサイズ(上記コードではnEnd)を与える必要があります。

ベンチマークとその結果

コード: find-max.js

find-max.js

function findMax0(nums, start, end, minValue = -Infinity) {
  let maxValue = minValue;
  for (let i = start; i < end; i++) {
    maxValue = Math.max(maxValue, nums[i]);
  }
  return maxValue;
}


function createMaxTree(nums, start = 0, end = nums.length) {
  const length = end - start;
  if (length === 1) return {max: nums[start], start, end};
  const mid = start + (length >> 1);
  const left = createMaxTree(nums, start, mid);
  const right = createMaxTree(nums, mid, end);
  // [start, end)範囲での最大値がmax
  return {max: Math.max(left.max, right.max), start, end, left, right};
}

function findMax(tree, start, end, minValue = -Infinity) {
  if (end <= tree.start || tree.end <= start) return minValue; // ノードの範囲が完全に範囲外
  if (start <= tree.start && tree.end <= end) return tree.max; // ノードの範囲が完全に範囲内
  // 部分的に範囲内
  const left = findMax(tree.left, start, end, minValue);   
  const right = findMax(tree.right, start, end, minValue); 
  return Math.max(left, right);
}


function createMaxArray(
  nums, start = 0, end = nums.length,
  array = new Array((1 << (Math.ceil(Math.log2(nums.length)) + 1)) - 1), i = 0) {
  const length = end - start;
  if (length === 1) {
    array[i] = nums[start];
    return array;
  }
  const mid = start + (length >> 1);
  const leftI = i * 2 + 1, rightI = leftI + 1;
  createMaxArray(nums, start, mid, array, leftI);
  createMaxArray(nums, mid, end, array, rightI);
  array[i] = Math.max(array[leftI], array[rightI]);
  return array;
}

function findMaxArray(array, nStart, nEnd, start, end, minValue = -Infinity, i = 0) {
  if (end <= nStart || nEnd <= start) return minValue; // ノードの範囲が完全に範囲外
  if (start <= nStart && nEnd <= end) return array[i]; // ノードの範囲が完全に範囲内
  // 部分的に範囲内
  const mid = nStart + ((nEnd - nStart) >> 1);
  const leftI = i * 2 + 1, rightI = leftI + 1;
  const left = findMaxArray(array, nStart, mid, start, end, minValue, leftI);
  const right = findMaxArray(array, mid, nEnd, start, end, minValue, rightI);
  return Math.max(left, right);
}

{
  const values = [...Array(30000).keys()].map(v => Math.random());
  const mid = values.length >> 1;
  const maxes0 = [];
  performance.mark("linear:start");
  for (let i = 0; i < values.length; i++) {
    const start = Math.min(i, mid), end = Math.max(i, mid);
    maxes0.push(findMax0(values, start, end, 0));
  }
  performance.mark("linear:end");
  
  const maxes = [];
  performance.mark("tree:start");
  const tree = createMaxTree(values);
  performance.mark("tree:created");  
  for (let i = 0; i < values.length; i++) {
    const start = Math.min(i, mid), end = Math.max(i, mid);
    maxes.push(findMax(tree, start, end, 0));
  }
  performance.mark("tree:end");
  
  const maxesA = [];
  performance.mark("array:start");
  const array = createMaxArray(values);
  performance.mark("array:created");
  for (let i = 0; i < values.length; i++) {
    const start = Math.min(i, mid), end = Math.max(i, mid);
    maxesA.push(findMaxArray(array, 0, values.length, start, end, 0));
  }
  performance.mark("array:end");

  console.log(maxes.every((m, i) => m === maxes0[i]));
  console.log(maxes.every((m, i) => m === maxesA[i]));
  
  performance.measure("linear", "linear:start", "linear:end");
  performance.measure("tree", "tree:start", "tree:end");
  performance.measure("tree:create", "tree:start", "tree:created");
  performance.measure("tree:find", "tree:created", "tree:end");
  performance.measure("array", "array:start", "array:end");
  performance.measure("array:create", "array:start", "array:created");
  performance.measure("array:find", "array:created", "array:end");

  console.log(performance.getEntriesByName("linear")[0]);
  console.log(performance.getEntriesByName("tree")[0]);
  console.log(performance.getEntriesByName("tree:create")[0]);
  console.log(performance.getEntriesByName("tree:find")[0]);
  console.log(performance.getEntriesByName("array")[0]);
  console.log(performance.getEntriesByName("array:create")[0]);
  console.log(performance.getEntriesByName("array:find")[0]);
}

実行結果

$ deno run --allow-hrtime find-max.js
true
true
PerformanceMeasure {
  name: "linear",
  entryType: "measure",
  startTime: 34.373083,
  duration: 188.385333,
  detail: null
}
PerformanceMeasure {
  name: "tree",
  entryType: "measure",
  startTime: 223.589083,
  duration: 18.106583,
  detail: null
}
PerformanceMeasure {
  name: "tree:create",
  entryType: "measure",
  startTime: 223.589083,
  duration: 6.16508300000001,
  detail: null
}
PerformanceMeasure {
  name: "tree:find",
  entryType: "measure",
  startTime: 229.754166,
  duration: 11.94149999999999,
  detail: null
}
PerformanceMeasure {
  name: "array",
  entryType: "measure",
  startTime: 241.722958,
  duration: 13.832333000000006,
  detail: null
}
PerformanceMeasure {
  name: "array:create",
  entryType: "measure",
  startTime: 241.722958,
  duration: 2.6689580000000035,
  detail: null
}
PerformanceMeasure {
  name: "array:find",
  entryType: "measure",
  startTime: 244.391916,
  duration: 11.163375000000002,
  detail: null
}
$

3万要素で、線形検索だと188.8かかるのが、二分木だと11.9、二分木配列だと11.2かかるだけになりました。