problems/range-minimum-query.html at master · chaoxu/problems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
<!DOCTYPE html>
<html lang="en">
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1">
    <meta name="description" content="Problems">
    <meta name="author" content="Chao Xu">
    <meta property="og:title" content="Range Minimum Query" />
    <meta property="og:type" content="article" />
    <meta property="og:site_name" content="Problems" />
    <meta property="article:tag" content="" />
    <title>Range Minimum Query</title>

    <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.11.0/dist/katex.min.css" integrity="sha384-BdGj8xC2eZkQaxoQ8nSLefg4AV4/AwB3Fj+8SUSo7pnKP6Eoy18liIKTPn9oBYNG" crossorigin="anonymous">

    <!-- The loading of KaTeX is deferred to speed up page rendering -->
    <script defer src="https://cdn.jsdelivr.net/npm/katex@0.11.0/dist/katex.min.js" integrity="sha384-JiKN5O8x9Hhs/UE5cT5AAJqieYlOZbGT3CHws/y97o3ty4R7/O5poG9F3JoiOYw1" crossorigin="anonymous"></script>

    <!-- To automatically render math in text elements, include the auto-render extension: -->
    <!-- <script defer src="https://cdn.jsdelivr.net/npm/katex@0.11.0/dist/contrib/auto-render.min.js" integrity="sha384-kWPLUVMOks5AQFrykwIup5lo0m3iMkkHrD0uJ4H5cjeGihAutqP0yW0J6dpFiVkI" crossorigin="anonymous"
        onload="renderMathInElement(document.body);"></script>
    -->
    <script defer>
      function render_katex_math(){
        const macros={
                      "\\C":"\\mathbb{C}",
                      "\\F":"\\mathbb{F}",
                      "\\e": "\\varepsilon",
                      "\\eps": "\\varepsilon",
                      "\\mex": "\\mathop{\\operatorname{mex}}",
                      "\\lcm": "\\mathop{\\operatorname{lcm}}",
                      "\\dist": "\\mathop{\\operatorname{dist}}",
                      "\\bigtriangleright": "{\\mathop{\\Large \\triangleright}}",
                      "\\bigtriangleleft": "{\\mathop{\\Large \\triangleleft}}",
                      '\\set':'\\left\\{ #1 \\right\\}',
                      '\\floor':'\\left\\lfloor #1 \\right\\rfloor',
                      '\\ceil':'\\left\\lceil #1 \\right\\rceil',
                      '\\abs':'\\left\\| #1 \\right\\|'
                      };
        const mathElements = document.getElementsByClassName("math");
        for (var i = 0; i < mathElements.length; i++) {
                  var texText = mathElements[i].firstChild;
                  if (mathElements[i].tagName == "SPAN") {
                   katex.render(texText.data, mathElements[i],
                    { displayMode: mathElements[i].classList.contains("display"), throwOnError: false, macros:macros}
                  );
                }
        };
      };
      window.onload = render_katex_math;
    </script>

  <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico"/>
  <link rel="stylesheet" href="/css/default.css" crossorigin="anonymous">
  <link rel="stylesheet" href="/css/blog.css" crossorigin="anonymous">
  </head>
  <body>
    <header class="hide-on-print">
        <div id="site-title">
            <a href="/">Problems</a>
        </div>
    </header>
    <!--<nav class="hide-on-print">
      <ul>
        <li><a href="/">Home</a></li>
      </ul>
    </nav>-->
    <main>
      <article>
        <h1 id="article-title">Range Minimum Query</h1>
        <br />
<div>
<h1 id="problem">Problem</h1>
<h2 id="preprocess">Preprocess</h2>
<p>An sequence <span class="math inline">a_1,\ldots,a_n</span> of totally ordered elements.</p>
<h2 id="queries">Queries</h2>
<ul>
<li><span class="math inline">minimum(j,k)</span> return <span class="math inline">t</span>, such that <span class="math inline">a_t=\min( \{a_j,\ldots,a_k\})</span> and <span class="math inline">j\leq t\leq k</span>.</li>
</ul>
<h1 id="algorithm">Algorithm</h1>
<p>Parameters: <span class="math inline">n</span> is the length of the sequence.</p>
</div>
<div class="hide-on-print">
    <div class="info">Tags: .</div>
</div>
      </article>
    </main>
    <!--
    <footer class="hide-on-print">© 2010 - <time><script>document.write(new Date().getFullYear())</script></time> <a href="https://chaoxuprime.com" rel="author">Chao Xu</a>. Licensed under a <a rel="license" href="http://creativecommons.org/licenses/by/4.0/">Creative Commons Attribution 4.0 International License</a>.
    </footer>
    -->
  </body>
</html>