md-array_perf.cs

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Numerics;

BenchmarkRunner.Run<Query>();

public class Query
{
    const int max = (int)1e9;
    const int n = 500000;

    int[] a;
    (int, int)[] q;
    SparseTable<int> st;
    SparseTableN<int> st2;

    [GlobalSetup]
    public void Setup()
    {

        var rn = new Random();
        a = new int[n];
        q = new (int, int)[n];
        for (int i = 0; i < a.Length; i++)
        {
            a[i] = rn.Next(max);
            var l = rn.Next(n);
            var r = rn.Next(l, n) + 1;
            q[i] = (l, r);
        }

        st = new SparseTable<int>(a);
        st2 = new SparseTableN<int>(a);
    }

    [Benchmark]
    public void JaggedArray()
    {
        for (int i = 0; i < q.Length; i++)
        {
            var (l, r) = q[i];
            st.RangeMin(l, r);
        }
    }

    [Benchmark]
    public void MDArray()
    {
        for (int i = 0; i < q.Length; i++)
        {
            var (l, r) = q[i];
            st2.RangeMin(l, r);
        }
    }
}

public class SparseTable<T> where T : INumber<T>
{
    T[][] buffer;
    int[] log2;

    public SparseTable(T[] init)
    {
        var n = init.Length;

        log2 = new int[n + 1];
        log2[0] = -1;
        for (int i = 2; i < log2.Length; i++) log2[i] = log2[i >> 1] + 1;

        buffer = new T[log2[n] + 1][];
        for (int i = 0; i < buffer.Length; i++) buffer[i] = new T[n - (1 << i) + 1];

        Array.Copy(init, 0, buffer[0], 0, init.Length);
        for (int i = 1, p = 1; i < buffer.Length; i++, p <<= 1)
            for (int j = 0; j < buffer[i].Length; j++)
                buffer[i][j] = T.Min(buffer[i - 1][j], buffer[i - 1][j + p]);
    }

    public T RangeMin(int l, int r)
    {
        var h = log2[r - l];
        return T.Min(buffer[h][l], buffer[h][r - (1 << h)]);
    }
}

public class SparseTableN<T> where T : INumber<T>
{
    T[,] buffer;
    int[] log2;

    public SparseTableN(T[] init)
    {
        var n = init.Length;

        log2 = new int[n + 1];
        log2[0] = -1;
        for (int i = 2; i < log2.Length; i++) log2[i] = log2[i >> 1] + 1;

        buffer = new T[log2[n] + 1, n];
        for (int i = 0; i < init.Length; i++) buffer[0, i] = init[i];

        for (int i = 1, p = 1; i < log2[n] + 1; i++, p <<= 1)
        {
            var len = n - (1 << i) + 1;
            for (int j = 0; j < len; j++) buffer[i, j] = T.Min(buffer[i - 1, j], buffer[i - 1, j + p]);
        }
    }

    public T RangeMin(int l, int r)
    {
        var h = log2[r - l];
        return T.Min(buffer[h, l], buffer[h, r - (1 << h)]);
    }
}

// * Summary *

BenchmarkDotNet=v0.13.2, OS=Windows 11 (10.0.22000.1335/21H2)
12th Gen Intel Core i7-12700, 1 CPU, 20 logical and 12 physical cores
.NET SDK=7.0.101
  [Host]     : .NET 7.0.1 (7.0.122.56804), X64 RyuJIT AVX2
  DefaultJob : .NET 7.0.1 (7.0.122.56804), X64 RyuJIT AVX2


|      Method |       Mean |    Error |   StdDev |
|------------ |-----------:|---------:|---------:|
| JaggedArray |   932.3 us |  8.94 us |  8.36 us |
|     MDArray | 2,946.8 us | 29.02 us | 25.73 us |