You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{"payload":{"allShortcutsEnabled":false,"path":"Sparse Table","repo":{"id":281201167,"defaultBranch":"master","name":"swift-algorithm-club","ownerLogin":"phantomato","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2020-07-20T18:54:36.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/2765174?v=4","public":true,"private":false,"isOrgOwned":false},"currentUser":null,"refInfo":{"name":"master","listCacheKey":"v0:1615913064.636359","canEdit":false,"refType":"branch","currentOid":"bcd9eb3e6b8bb7c8f67eb962b065b16ef5c9f25b"},"tree":{"items":[{"name":"Images","path":"Sparse Table/Images","contentType":"directory"},{"name":"Sparse Table.playground","path":"Sparse Table/Sparse Table.playground","contentType":"directory"},{"name":"README.markdown","path":"Sparse Table/README.markdown","contentType":"file"}],"templateDirectorySuggestionUrl":null,"readme":{"displayName":"README.markdown","richText":"\u003carticle class=\"markdown-body entry-content container-lg\" itemprop=\"text\"\u003e\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch1 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eSparse Table\u003c/h1\u003e\u003ca id=\"user-content-sparse-table\" class=\"anchor\" aria-label=\"Permalink: Sparse Table\" href=\"#sparse-table\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eI'm excited to present \u003cstrong\u003eSparse Tables\u003c/strong\u003e. Despite being somewhat niche, Sparse Tables are simple to implement and extremely powerful.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eThe Problem\u003c/h3\u003e\u003ca id=\"user-content-the-problem\" class=\"anchor\" aria-label=\"Permalink: The Problem\" href=\"#the-problem\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eLet's suppose:\u003c/p\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003ewe have an array \u003cstrong\u003ea\u003c/strong\u003e of some type\u003c/li\u003e\n\u003cli\u003ewe have some associative binary function \u003cstrong\u003ef\u003c/strong\u003e \u003csup\u003e[*]\u003c/sup\u003e. The function can be: min, max, \u003ca href=\"/phantomato/swift-algorithm-club/blob/master/GCD\"\u003egcd\u003c/a\u003e, boolean AND, boolean OR ...\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp dir=\"auto\"\u003e\u003cem\u003e\u003csup\u003e[*]\u003c/sup\u003e where \u003cstrong\u003ef\u003c/strong\u003e is also \"idempotent\". Don't worry, I'll explain this in a moment.\u003c/em\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eOur task is as follows:\u003c/p\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003eGiven two indices \u003cstrong\u003el\u003c/strong\u003e and \u003cstrong\u003er\u003c/strong\u003e, answer a \u003cstrong\u003equery\u003c/strong\u003e for the interval \u003ccode\u003e[l, r)\u003c/code\u003e by performing \u003ccode\u003ef(a[l], a[l + 1], a[l + 2], ..., a[r - 1])\u003c/code\u003e; taking all the elements in the range and applying \u003cstrong\u003ef\u003c/strong\u003e to them\u003c/li\u003e\n\u003cli\u003eThere will be a \u003cem\u003ehuge\u003c/em\u003e number \u003cstrong\u003eQ\u003c/strong\u003e of these queries to answer ... so we should be able to answer each query \u003cem\u003equickly\u003c/em\u003e!\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp dir=\"auto\"\u003eFor example, if we have an array of numbers:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"var a = [ 20, 3, -1, 101, 14, 29, 5, 61, 99 ]\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ea\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e20\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e3\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e101\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e14\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e29\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e5\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e61\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e99\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eand our function \u003cstrong\u003ef\u003c/strong\u003e is the \u003cem\u003emin\u003c/em\u003e function.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThen we may be given a query for interval \u003ccode\u003e[3, 8)\u003c/code\u003e. That means we look at the elements:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"101, 14, 29, 5, 61\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e101, 14, 29, 5, 61\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003ebecause these are the elements of \u003cstrong\u003ea\u003c/strong\u003e with indices\nthat lie in our range \u003ccode\u003e[3, 8)\u003c/code\u003e – elements from index 3 up to, but not including, index 8.\nWe then we pass all of these numbers into the min function,\nwhich takes the minimum. The answer to the query is \u003ccode\u003e5\u003c/code\u003e, because that's the result of \u003ccode\u003emin(101, 14, 29, 5, 61)\u003c/code\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eImagine we have millions of these queries to process.\u003c/p\u003e\n\u003cblockquote\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e\u003cem\u003eQuery 1\u003c/em\u003e: Find minimum of all elements between 2 and 5\u003c/li\u003e\n\u003cli\u003e\u003cem\u003eQuery 2\u003c/em\u003e: Find minimum of all elements between 3 and 9\u003c/li\u003e\n\u003cli\u003e...\u003c/li\u003e\n\u003cli\u003e\u003cem\u003eQuery 1000000\u003c/em\u003e: Find minimum of all elements between 1 and 4\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/blockquote\u003e\n\u003cp dir=\"auto\"\u003eAnd our array is very large. Here, let's say \u003cstrong\u003eQ\u003c/strong\u003e = 1000000 and \u003cstrong\u003eN\u003c/strong\u003e = 500000. Both numbers are \u003cem\u003ehuge\u003c/em\u003e. We want to make sure that we can answer each query really quickly, or else the number of queries will overwhelm us!\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003cem\u003eSo that's the problem.\u003c/em\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe naive solution to this problem is to perform a \u003ccode\u003efor\u003c/code\u003e loop\nto compute the answer for each query. However, for very large \u003cstrong\u003eQ\u003c/strong\u003e and very large \u003cstrong\u003eN\u003c/strong\u003e this\nwill be too slow. We can speed up the time to compute the answer by using a data structure called\na \u003cstrong\u003eSparse Table\u003c/strong\u003e. You'll notice that so far, our problem is exactly the same as that of the \u003ca href=\"https://github.com/raywenderlich/swift-algorithm-club/tree/master/Segment%20Tree\"\u003eSegment Tree\u003c/a\u003e\n(assuming you're familiar). However! ... there's one crucial difference between Segment Trees\nand Sparse Tables ... and it concerns our choice of \u003cstrong\u003ef\u003c/strong\u003e.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eA small gotcha ... Idempotency\u003c/h3\u003e\u003ca id=\"user-content-a-small-gotcha--idempotency\" class=\"anchor\" aria-label=\"Permalink: A small gotcha ... Idempotency\" href=\"#a-small-gotcha--idempotency\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eSuppose we wanted to find the answer to \u003cstrong\u003e\u003ccode\u003e[A, D)\u003c/code\u003e\u003c/strong\u003e.\nAnd we already know the answer to two ranges \u003cstrong\u003e\u003ccode\u003e[A, B)\u003c/code\u003e\u003c/strong\u003e and \u003cstrong\u003e\u003ccode\u003e[C, D)\u003c/code\u003e\u003c/strong\u003e.\nAnd importantly here, ... \u003cem\u003ethese ranges overlap\u003c/em\u003e!! We have \u003cstrong\u003eC\u003c/strong\u003e \u0026lt; \u003cstrong\u003eB\u003c/strong\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/phantomato/swift-algorithm-club/blob/master/Sparse%20Table/Images/idempotency.png\"\u003e\u003cimg src=\"/phantomato/swift-algorithm-club/raw/master/Sparse%20Table/Images/idempotency.png\" alt=\"Overlapping ranges\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eSo what? Well, for \u003cstrong\u003ef\u003c/strong\u003e = minimum function, we can take our answers for \u003cstrong\u003e\u003ccode\u003e[A, B)\u003c/code\u003e\u003c/strong\u003e and \u003cstrong\u003e\u003ccode\u003e[C, D)\u003c/code\u003e\u003c/strong\u003e\nand combine them!\nWe can just take the minimum of the two answers: \u003ccode\u003eresult = min(x1, x2)\u003c/code\u003e ... \u003cem\u003evoilà!\u003c/em\u003e, we have the minimum for \u003cstrong\u003e\u003ccode\u003e[A, D)\u003c/code\u003e\u003c/strong\u003e.\nIt didn't matter that the intervals overlap - we still found the correct minimum.\nBut now suppose \u003cstrong\u003ef\u003c/strong\u003e is the addition operation \u003ccode\u003e+\u003c/code\u003e. Ok, so now we're taking sums over ranges.\nIf we tried the same approach again, it wouldn't work. That is,\nif we took our answers for \u003cstrong\u003e\u003ccode\u003e[A, B)\u003c/code\u003e\u003c/strong\u003e and \u003cstrong\u003e\u003ccode\u003e[C, D)\u003c/code\u003e\u003c/strong\u003e\nand added them together we'd get a wrong answer for \u003cstrong\u003e\u003ccode\u003e[A, D)\u003c/code\u003e\u003c/strong\u003e.\n\u003cem\u003eWhy?\u003c/em\u003e Well, we'd have counted some elements twice because of the overlap.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eLater, we'll see that in order to answer queries, Sparse Tables use this very technique.\nThey combine answers in the same way as shown above. Unfortunately this means\nwe have to exclude certain binary operators from being \u003cstrong\u003ef\u003c/strong\u003e, including \u003ccode\u003e+\u003c/code\u003e, \u003ccode\u003e*\u003c/code\u003e, XOR, ...\nbecause they don't work with this technique.\nIn order to get the best speed of a Sparse Table,\nwe need to make sure that the \u003cstrong\u003ef\u003c/strong\u003e we're using is an \u003cstrong\u003e\u003ca href=\"https://en.wikipedia.org/wiki/Idempotence\" rel=\"nofollow\"\u003eidempotent\u003c/a\u003e\u003c/strong\u003e binary operator.\nMathematically, these are operators that satisfy \u003ccode\u003ef(x, x) = x\u003c/code\u003e for all possible \u003cstrong\u003ex\u003c/strong\u003e that could be in \u003cstrong\u003ea\u003c/strong\u003e.\nPractically speaking, these are the only operators that work; allowing us to combine answers from overlapping ranges.\nExamples of idempotent \u003cstrong\u003ef\u003c/strong\u003e's are min, max, gcd, boolean AND, boolean OR, bitwise AND and bitwise OR.\nNote that for Segment Trees, \u003cstrong\u003ef\u003c/strong\u003e does not have to be idempotent. That's the crucial difference between\nSegment Trees and Sparse Tables.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003cem\u003ePhew!\u003c/em\u003e Now that we've got that out of the way, let's dive in!\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eStructure of a Sparse Table\u003c/h2\u003e\u003ca id=\"user-content-structure-of-a-sparse-table\" class=\"anchor\" aria-label=\"Permalink: Structure of a Sparse Table\" href=\"#structure-of-a-sparse-table\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eLet's use \u003cstrong\u003ef\u003c/strong\u003e = min and use the array:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"var a = [ 10, 6, 5, -7, 9, -8, 2, 4, 20 ]\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ea\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e10\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e6\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e5\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e7\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e9\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e8\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e4\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e20\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eIn this case, the Sparse Table looks like this:\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/phantomato/swift-algorithm-club/blob/master/Sparse%20Table/Images/structure.png\"\u003e\u003cimg src=\"/phantomato/swift-algorithm-club/raw/master/Sparse%20Table/Images/structure.png\" alt=\"Sparse Table\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eWhat's going on here? There seems to be loads of intervals.\n\u003cem\u003eCorrect!\u003c/em\u003e Sparse tables are preloaded with the answers for lots of queries \u003ccode\u003e[l, r)\u003c/code\u003e.\nHere's the idea. Before we process our \u003cstrong\u003eQ\u003c/strong\u003e queries, we'll pre-populate our Sparse Table \u003ccode\u003etable\u003c/code\u003e\nwith answers to loads of queries;\nmaking it act a bit like a \u003cem\u003ecache\u003c/em\u003e. When we come to answer one of our queries, we can break the query\ndown into smaller \"sub-queries\", each having an answer that's already in the cache.\nWe lookup the cached answers for the sub-queries in\n\u003ccode\u003etable\u003c/code\u003e in constant time\nand combine the answers together\nto give the overall answer to the original query in speedy time.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe problem is, we can't store the answers for every single possible query that we could ever have ...\nor else our table would be too big! After all, our Sparse Table needs to be \u003cem\u003esparse\u003c/em\u003e. So what do we do?\nWe only pick the \"best\" intervals to store answers for. And as it turns out, the \"best\" intervals are those\nthat have a \u003cstrong\u003ewidth that is a power of two\u003c/strong\u003e!\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eFor example, the answer for the query \u003ccode\u003e[10, 18)\u003c/code\u003e is in our table\nbecause the interval width: \u003ccode\u003e18 - 10 = 8 = 2**3\u003c/code\u003e is a power of two (\u003ccode\u003e**\u003c/code\u003e is the \u003ca href=\"https://en.wikipedia.org/wiki/Exponentiation\" rel=\"nofollow\"\u003eexponentiation operator\u003c/a\u003e).\nAlso, the answer for \u003ccode\u003e[15, 31)\u003c/code\u003e is in our table because its width: \u003ccode\u003e31 - 15 = 16 = 2**4\u003c/code\u003e is again a power of two.\nHowever, the answer for \u003ccode\u003e[1, 6)\u003c/code\u003e is \u003cem\u003enot\u003c/em\u003e in there because the interval's width: \u003ccode\u003e6 - 1 = 5\u003c/code\u003e is \u003cem\u003enot\u003c/em\u003e a power of two.\nConsequently, we don't store answers for \u003cem\u003eall\u003c/em\u003e possible intervals that fit inside \u003cstrong\u003ea\u003c/strong\u003e –\nonly the ones with a width that is a power of two.\nThis is true irrespective of where the interval starts within \u003cstrong\u003ea\u003c/strong\u003e.\nWe'll gradually see that this approach works and that relatively speaking, it uses very little space.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eA \u003cstrong\u003eSparse Table\u003c/strong\u003e is a table where \u003ccode\u003etable[w][l]\u003c/code\u003e contains the answer for \u003ccode\u003e[l, l + 2**w)\u003c/code\u003e.\u003cbr\u003e\nIt has entries \u003ccode\u003etable[w][l]\u003c/code\u003e where:\u003c/p\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e\u003cstrong\u003ew\u003c/strong\u003e tells us our \u003cstrong\u003ewidth\u003c/strong\u003e ... the number of elements or the \u003cem\u003ewidth\u003c/em\u003e is \u003ccode\u003e2**w\u003c/code\u003e\u003c/li\u003e\n\u003cli\u003e\u003cstrong\u003el\u003c/strong\u003e tells us the \u003cstrong\u003elower bound\u003c/strong\u003e ... it's the starting point of our interval\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp dir=\"auto\"\u003eSome examples:\u003c/p\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e\u003ccode\u003etable[3][0] = -8\u003c/code\u003e: our width is \u003ccode\u003e2**3\u003c/code\u003e, we start at \u003ccode\u003el = 0\u003c/code\u003e so our query is \u003ccode\u003e[0, 0 + 2**3) = [0, 8)\u003c/code\u003e.\u003cbr\u003e\nThe answer for this query is \u003ccode\u003emin(10, 6, 5, -7, 9, -8, 2, 4, 20) = -8\u003c/code\u003e.\u003c/li\u003e\n\u003cli\u003e\u003ccode\u003etable[2][1] = -7\u003c/code\u003e: our width is \u003ccode\u003e2**2\u003c/code\u003e, we start at \u003ccode\u003el = 1\u003c/code\u003e so our query is \u003ccode\u003e[1, 1 + 2**2) = [1, 5)\u003c/code\u003e.\u003cbr\u003e\nThe answer for this query is \u003ccode\u003emin(6, 5, -7, 9) = -7\u003c/code\u003e.\u003c/li\u003e\n\u003cli\u003e\u003ccode\u003etable[1][7] = 4\u003c/code\u003e: our width is \u003ccode\u003e2**1\u003c/code\u003e, we start at \u003ccode\u003el = 7\u003c/code\u003e so our query is \u003ccode\u003e[7, 7 + 2**1) = [7, 9)\u003c/code\u003e.\u003cbr\u003e\nThe answer for this query is \u003ccode\u003emin(4, 20) = 4\u003c/code\u003e.\u003c/li\u003e\n\u003cli\u003e\u003ccode\u003etable[0][8] = 20\u003c/code\u003e: our width is \u003ccode\u003e2**0\u003c/code\u003e, we start at \u003ccode\u003el = 8\u003c/code\u003e so our query is\u003ccode\u003e[8, 8 + 2**0) = [8, 9)\u003c/code\u003e.\u003cbr\u003e\nThe answer for this query is \u003ccode\u003emin(20) = 20\u003c/code\u003e.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/phantomato/swift-algorithm-club/blob/master/Sparse%20Table/Images/structure_examples.png\"\u003e\u003cimg src=\"/phantomato/swift-algorithm-club/raw/master/Sparse%20Table/Images/structure_examples.png\" alt=\"Sparse Table\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eA Sparse Table can be implemented using a \u003ca href=\"/phantomato/swift-algorithm-club/blob/master/2D%20Array\"\u003etwo-dimentional array\u003c/a\u003e.\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"public class SparseTable\u0026lt;T\u0026gt; {\n private var table: [[T]]\n\n public init(array: [T], function: @escaping (T, T) -\u0026gt; T, defaultT: T) {\n table = [[T]](repeating: [T](repeating: defaultT, count: N), count: W)\n }\n // ... \n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003epublic\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eclass\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eSparseTable\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003eT\u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eprivate\u003c/span\u003e \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003e\u003cspan class=\"pl-c1\"\u003etable\u003c/span\u003e\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003epublic\u003c/span\u003e \u003cspan class=\"pl-v\"\u003einit\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003earray\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e function\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-k\"\u003e@escaping\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e defaultT\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n table \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eT\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003erepeating\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eT\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003erepeating\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e defaultT\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e count\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e N\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e count\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e W\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n // ... \n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eBuilding a Sparse Table\u003c/h2\u003e\u003ca id=\"user-content-building-a-sparse-table\" class=\"anchor\" aria-label=\"Permalink: Building a Sparse Table\" href=\"#building-a-sparse-table\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eTo build a Sparse Table, we compute each table entry starting from the bottom-left and moving up towards\nthe top-right (in accordance with the diagram).\nFirst we'll compute all the intervals for \u003cstrong\u003ew\u003c/strong\u003e = 0, then compute all the intervals\nand for \u003cstrong\u003ew\u003c/strong\u003e = 1 and so on. We'll continue up until \u003cstrong\u003ew\u003c/strong\u003e is big enough such that our intervals are can cover at least half the array.\nFor each \u003cstrong\u003ew\u003c/strong\u003e, we compute the interval for \u003cstrong\u003el\u003c/strong\u003e = 0, 1, 2, 3, ... until we reach \u003cstrong\u003eN\u003c/strong\u003e.\nThis is all achieved using a double \u003ccode\u003efor\u003c/code\u003e-\u003ccode\u003ein\u003c/code\u003e loop:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"for w in 0..\u0026lt;W {\n for l in 0..\u0026lt;N {\n // compute table[w][l]\n }\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ew\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ein\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e..\u0026lt;\u003c/span\u003eW \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003el\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ein\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e..\u0026lt;\u003c/span\u003eN \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n // compute table[w][l]\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eTo compute \u003ccode\u003etable[w][l]\u003c/code\u003e:\u003c/p\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e\u003cstrong\u003eBase Case (w = 0)\u003c/strong\u003e: Each interval has width \u003ccode\u003e2**w = 1\u003c/code\u003e.\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003eWe have \u003cem\u003eone\u003c/em\u003e element intervals of the form: \u003ccode\u003e[l, l + 1)\u003c/code\u003e.\u003c/li\u003e\n\u003cli\u003eThe answer is just \u003ccode\u003ea[l]\u003c/code\u003e (e.g. the minimum of over a list with one element\nis just the element itself).\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"table[w][l] = a[l]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003etable[w][l] = a[l]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/li\u003e\n\u003cli\u003e\u003cstrong\u003eInductive Case (w \u0026gt; 0)\u003c/strong\u003e: We need to find out the answer to \u003ccode\u003e[l, l + 2**w)\u003c/code\u003e for some \u003cstrong\u003el\u003c/strong\u003e.\nThis interval, like all of our intervals in our table has a width that\nis a power of two (e.g. 2, 4, 8, 16) ... so we can cut it into two equal halves.\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003eOur interval with width \u003ccode\u003e2**w\u003c/code\u003e is cut into two intervals, each of width \u003ccode\u003e2**(w - 1)\u003c/code\u003e.\u003c/li\u003e\n\u003cli\u003eBecause each half has a width that is a power of two, we can look them up in our Sparse Table.\u003c/li\u003e\n\u003cli\u003eWe combine them together using \u003cstrong\u003ef\u003c/strong\u003e.\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"table[w][l] = f(table[w - 1][l], table[w - 1][l + 2 ** (w - 1)])\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003etable[w][l] = f(table[w - 1][l], table[w - 1][l + 2 ** (w - 1)])\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/phantomato/swift-algorithm-club/blob/master/Sparse%20Table/Images/recursion.png\"\u003e\u003cimg src=\"/phantomato/swift-algorithm-club/raw/master/Sparse%20Table/Images/recursion.png\" alt=\"Sparse Table\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eFor example for \u003ccode\u003ea = [ 10, 6, 5, -7, 9, -8, 2, 4, 20 ]\u003c/code\u003e and \u003cstrong\u003ef\u003c/strong\u003e = \u003cem\u003emin\u003c/em\u003e:\u003c/p\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003ewe compute \u003ccode\u003etable[0][2] = 5\u003c/code\u003e. We just had to look at \u003ccode\u003ea[2]\u003c/code\u003e because the range has a width of one.\u003c/li\u003e\n\u003cli\u003ewe compute \u003ccode\u003etable[1][7] = 4\u003c/code\u003e. We looked at \u003ccode\u003etable[0][7]\u003c/code\u003e and \u003ccode\u003etable[0][8]\u003c/code\u003e and apply \u003cstrong\u003ef\u003c/strong\u003e to them.\u003c/li\u003e\n\u003cli\u003ewe compute \u003ccode\u003etable[3][1] = -8\u003c/code\u003e. We looked at \u003ccode\u003etable[2][1]\u003c/code\u003e and \u003ccode\u003etable[2][5]\u003c/code\u003e and apply \u003cstrong\u003ef\u003c/strong\u003e to them.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/phantomato/swift-algorithm-club/blob/master/Sparse%20Table/Images/recursion_examples.png\"\u003e\u003cimg src=\"/ph
8000
antomato/swift-algorithm-club/raw/master/Sparse%20Table/Images/recursion_examples.png\" alt=\"Sparse Table\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"public init(array: [T], function: @escaping (T, T) -\u0026gt; T, defaultT: T) {\n let N = array.count\n let W = Int(ceil(log2(Double(N))))\n table = [[T]](repeating: [T](repeating: defaultT, count: N), count: W)\n self.function = function\n self.defaultT = defaultT\n\n for w in 0..\u0026lt;W {\n for l in 0..\u0026lt;N {\n if w == 0 {\n table[w][l] = array[l]\n } else {\n let first = self.table[w - 1][l]\n let secondIndex = l + (1 \u0026lt;\u0026lt; (w - 1))\n let second = ((0..\u0026lt;N).contains(secondIndex)) ? table[w - 1][secondIndex] : defaultT\n table[w][l] = function(first, second)\n }\n }\n }\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003epublic\u003c/span\u003e \u003cspan class=\"pl-v\"\u003einit\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003earray\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e function\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-k\"\u003e@escaping\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e defaultT\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eN\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e array\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eW\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eceil\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-en\"\u003elog2\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eDouble\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eN\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n table \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eT\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003erepeating\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eT\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003erepeating\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e defaultT\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e count\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e N\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e count\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e W\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-smi\"\u003eself\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003efunction \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e function\n \u003cspan class=\"pl-smi\"\u003eself\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003edefaultT \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e defaultT\n\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ew\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ein\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e..\u0026lt;\u003c/span\u003eW \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003el\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ein\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e..\u0026lt;\u003c/span\u003eN \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e w \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003etable\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ew\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003el\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003earray\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003el\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003efirst\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eself\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003etable\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ew \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003el\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003esecondIndex\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e l \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e \u0026lt;\u0026lt; \u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ew \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003esecond\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e..\u0026lt;\u003c/span\u003eN\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003econtains\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003esecondIndex\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e?\u003c/span\u003e \u003cspan class=\"pl-en\"\u003etable\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ew \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003esecondIndex\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-k\"\u003e:\u003c/span\u003e defaultT\n \u003cspan class=\"pl-en\"\u003etable\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ew\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003el\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003efunction\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003efirst\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e second\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eBuilding a Sparse Table takes \u003cstrong\u003eO(NlogN)\u003c/strong\u003e time.\u003cbr\u003e\nThe table itself uses \u003cstrong\u003eO(NlgN)\u003c/strong\u003e additional space.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eGetting Answers to Queries\u003c/h2\u003e\u003ca id=\"user-content-getting-answers-to-queries\" class=\"anchor\" aria-label=\"Permalink: Getting Answers to Queries\" href=\"#getting-answers-to-queries\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eSuppose we've built our Sparse Table. And now we're going to process our \u003cstrong\u003eQ\u003c/strong\u003e queries.\nHere's where our work pays off.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eLet's suppose \u003cstrong\u003ef\u003c/strong\u003e = min and we have:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"var a = [ 10, 6, 5, -7, 9, -8, 2, 4, 20 ]\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ea\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e10\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e6\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e5\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e7\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e9\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e8\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e4\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e20\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eAnd we have a query \u003ccode\u003e[3, 9)\u003c/code\u003e.\u003c/p\u003e\n\u003col dir=\"auto\"\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eFirst let's find the largest power of two that fits inside \u003ccode\u003e[3, 9)\u003c/code\u003e. Our interval has width \u003ccode\u003e9 - 3 = 6\u003c/code\u003e. So the largest power of two that fits inside is four.\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eWe create two new queries of \u003ccode\u003e[3, 7)\u003c/code\u003e and \u003ccode\u003e[5, 9)\u003c/code\u003e that have a width of four.\nAnd, we arrange them so that to that they span the whole interval without leaving any gaps.\n\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/phantomato/swift-algorithm-club/blob/master/Sparse%20Table/Images/query_example.png\"\u003e\u003cimg src=\"/phantomato/swift-algorithm-club/raw/master/Sparse%20Table/Images/query_example.png\" alt=\"Sparse Table\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eBecause these two intervals have a width that is exactly a power of two we can lookup their answers in the Sparse Table using the\nentries for \u003cstrong\u003ew\u003c/strong\u003e = 2. The answer to \u003ccode\u003e[3, 7)\u003c/code\u003e is given by \u003ccode\u003etable[2][3]\u003c/code\u003e, and the answer to \u003ccode\u003e[5, 9)\u003c/code\u003e is given by \u003ccode\u003etable[2][5]\u003c/code\u003e.\nWe compute and return \u003ccode\u003emin(table[2][3], table[2][5])\u003c/code\u003e. This is our final answer! 🎉. Although the two intervals overlap, it doesn't matter because the \u003cstrong\u003ef\u003c/strong\u003e = min we originally chose is idempotent.\u003c/p\u003e\n\u003c/li\u003e\n\u003c/ol\u003e\n\u003cp dir=\"auto\"\u003eIn general, for each query: \u003ccode\u003e[l, r)\u003c/code\u003e ...\u003c/p\u003e\n\u003col dir=\"auto\"\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eFind \u003cstrong\u003eW\u003c/strong\u003e, by looking for the largest width that fits inside the interval that's also a power of two. Let largest such width = \u003ccode\u003e2**W\u003c/code\u003e.\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eForm two sub-queries of width \u003ccode\u003e2**W\u003c/code\u003e and arrange them to that they span the whole interval without leaving gaps.\nTo guarantee there are no gaps, we need to align one half to the left and the align other half to the right.\n\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/phantomato/swift-algorithm-club/blob/master/Sparse%20Table/Images/query.png\"\u003e\u003cimg src=\"/phantomato/swift-algorithm-club/raw/master/Sparse%20Table/Images/query.png\" alt=\"Sparse Table\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eCompute and return \u003ccode\u003ef(table[W][l], table[W][r - 2**W])\u003c/code\u003e.\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"public func query(from l: Int, until r: Int) -\u0026gt; T {\n let width = r - l\n let W = Int(floor(log2(Double(width))))\n let lo = table[W][l]\n let hi = table[W][r - (1 \u0026lt;\u0026lt; W)]\n return function(lo, hi)\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003epublic\u003c/span\u003e \u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e query\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003efrom l\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e until r\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ewidth\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e r \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e l\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eW\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-en\"\u003efloor\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-en\"\u003elog2\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eDouble\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ewidth\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elo\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003etable\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eW\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003el\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ehi\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003etable\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eW\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003er \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e \u0026lt;\u0026lt; W\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-en\"\u003efunction\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003elo\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e hi\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003c/li\u003e\n\u003c/ol\u003e\n\u003cp dir=\"auto\"\u003eFinding answers to queries takes \u003cstrong\u003eO(1)\u003c/strong\u003e time.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eAnalysing Sparse Tables\u003c/h2\u003e\u003ca id=\"user-content-analysing-sparse-tables\" class=\"anchor\" aria-label=\"Permalink: Analysing Sparse Tables\" href=\"#analysing-sparse-tables\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e\u003cstrong\u003eQuery Time\u003c/strong\u003e - Both table lookups take constant time. All other operations inside \u003ccode\u003equery\u003c/code\u003e take constant time.\nSo answering a single query also takes constant time: \u003cstrong\u003eO(1)\u003c/strong\u003e. But instead of one query we're actually answering \u003cstrong\u003eQ\u003c/strong\u003e queries,\nand we'll need time to built the table before-hand.\nOverall time is: \u003cstrong\u003eO(NlgN + Q)\u003c/strong\u003e to build the table and answer all queries.\nThe naive approach is to do a for loop for each query. The overall time for the naive approach is: \u003cstrong\u003eO(NQ)\u003c/strong\u003e.\nFor very large \u003cstrong\u003eQ\u003c/strong\u003e, the naive approach will scale poorly. For example if \u003ccode\u003eQ = O(N*N)\u003c/code\u003e\nthen the naive approach is \u003ccode\u003eO(N*N*N)\u003c/code\u003e where a Sparse Table takes time \u003ccode\u003eO(N*N)\u003c/code\u003e.\u003c/li\u003e\n\u003cli\u003e\u003cstrong\u003eSpace\u003c/strong\u003e- The number of possible \u003cstrong\u003ew\u003c/strong\u003e is \u003cstrong\u003elgN\u003c/strong\u003e and the number of possible \u003cstrong\u003el\u003c/strong\u003e our table is \u003cstrong\u003eN\u003c/strong\u003e. So the table\nhas uses \u003cstrong\u003eO(NlgN)\u003c/strong\u003e additional space.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eComparison with Segment Trees\u003c/h3\u003e\u003ca id=\"user-content-comparison-with-segment-trees\" class=\"anchor\" aria-label=\"Permalink: Comparison with Segment Trees\" href=\"#comparison-with-segment-trees\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e\u003cstrong\u003ePre-processing\u003c/strong\u003e - Segment Trees take \u003cstrong\u003eO(N)\u003c/strong\u003e time to build and use \u003cstrong\u003eO(N)\u003c/strong\u003e space. Sparse Tables take \u003cstrong\u003eO(NlgN)\u003c/strong\u003e time to build and use \u003cstrong\u003eO(NlgN)\u003c/strong\u003e space.\u003c/li\u003e\n\u003cli\u003e\u003cstrong\u003eQueries\u003c/strong\u003e - Segment Tree queries are \u003cstrong\u003eO(lgN)\u003c/strong\u003e time for any \u003cstrong\u003ef\u003c/strong\u003e (idempotent or not idempotent). Sparse Table queries are \u003cstrong\u003eO(1)\u003c/strong\u003e time if \u003cstrong\u003ef\u003c/strong\u003e is idempotent and are not supported if \u003cstrong\u003ef\u003c/strong\u003e is not idempotent. \u003csup\u003e[†]\u003c/sup\u003e\u003c/li\u003e\n\u003cli\u003e\u003cstrong\u003eReplacing Items\u003c/strong\u003e - Segment Trees allow us to efficiently update an element in \u003cstrong\u003ea\u003c/strong\u003e and update the segment tree in \u003cstrong\u003eO(lgN)\u003c/strong\u003e time. Sparse Tables do not allow this to be done efficiently. If we were to update an element in \u003cstrong\u003ea\u003c/strong\u003e, we'd have to rebuild the Sparse Table all over again in \u003cstrong\u003eO(NlgN)\u003c/strong\u003e time.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp dir=\"auto\"\u003e\u003csup\u003e[†]\u003c/sup\u003e \u003cem\u003eAlthough technically, it's possible to rewrite the \u003ccode\u003equery\u003c/code\u003e method\nto add support for non-idempotent functions. But in doing so, we'd bump up the time up from O(1) to O(lgn),\ncompletely defeating the original purpose of Sparse Tables - supporting lightening quick queries.\nIn such a case, we'd be better off using a Segment Tree (or a Fenwick Tree)\u003c/em\u003e\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eSummary\u003c/h2\u003e\u003ca id=\"user-content-summary\" class=\"anchor\" aria-label=\"Permalink: Summary\" href=\"#summary\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThat's it! See the playground for more examples involving Sparse Tables.\nYou'll see examples for: min, max, gcd, boolean operators and logical operators.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eSee also\u003c/h3\u003e\u003ca id=\"user-content-see-also\" class=\"anchor\" aria-label=\"Permalink: See also\" href=\"#see-also\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e\u003ca href=\"https://github.com/raywenderlich/swift-algorithm-club/tree/master/Segment%20Tree\"\u003eSegment Trees (Swift Algorithm Club)\u003c/a\u003e\u003c/li\u003e\n\u003cli\u003e\u003ca href=\"https://www.geeksforgeeks.org/range-sum-query-using-sparse-table/\" rel=\"nofollow\"\u003eHow to write O(lgn) time query function to support non-idempontent functions (GeeksForGeeks)\u003c/a\u003e\u003c/li\u003e\n\u003cli\u003e\u003ca href=\"https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/\" rel=\"nofollow\"\u003eFenwick Trees / Binary Indexed Trees (TopCoder)\u003c/a\u003e\u003c/li\u003e\n\u003cli\u003e\u003ca href=\"https://en.wikipedia.org/wiki/Semilattice\" rel=\"nofollow\"\u003eSemilattice (Wikipedia)\u003c/a\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp dir=\"auto\"\u003e\u003cem\u003eWritten for Swift Algorithm Club by \u003ca href=\"https://github.com/jameslawson\"\u003eJames Lawson\u003c/a\u003e\u003c/em\u003e\u003c/p\u003e\n\u003c/article\u003e","errorMessage":null,"headerInfo":{"toc":[{"level":1,"text":"Sparse Table","anchor":"sparse-table","htmlText":"Sparse Table"},{"level":3,"text":"The Problem","anchor":"the-problem","htmlText":"The Problem"},{"level":3,"text":"A small gotcha ... Idempotency","anchor":"a-small-gotcha--idempotency","htmlText":"A small gotcha ... Idempotency"},{"level":2,"text":"Structure of a Sparse Table","anchor":"structure-of-a-sparse-table","htmlText":"Structure of a Sparse Table"},{"level":2,"text":"Building a Sparse Table","anchor":"building-a-sparse-table","htmlText":"Building a Sparse Table"},{"level":2,"text":"Getting Answers to Queries","anchor":"getting-answers-to-queries","htmlText":"Getting Answers to Queries"},{"level":2,"text":"Analysing Sparse Tables","anchor":"analysing-sparse-tables","htmlText":"Analysing Sparse Tables"},{"level":3,"text":"Comparison with Segment Trees","anchor":"comparison-with-segment-trees","htmlText":"Comparison with Segment Trees"},{"level":2,"text":"Summary","anchor":"summary","htmlText":"Summary"},{"level":3,"text":"See also","anchor":"see-also","htmlText":"See also"}],"siteNavLoginPath":"/login?return_to=https%3A%2F%2Fgithub.com%2Fphantomato%2Fswift-algorithm-club%2Ftree%2Fmaster%2FSparse%2520Table"}},"totalCount":3,"showBranchInfobar":true},"fileTree":{"":{"items":[{"name":".github","path":".github","contentType":"directory"},{"name":"3Sum and 4Sum","path":"3Sum and 4Sum","contentType":"directory"},{"name":"AVL Tree","path":"AVL Tree","contentType":"directory"},{"name":"All-Pairs Shortest Paths","path":"All-Pairs Shortest Paths","contentType":"directory"},{"name":"Array2D","path":"Array2D","contentType":"directory"},{"name":"B-Tree","path":"B-Tree","contentType":"directory"},{"name":"Binary Search Tree","path":"Binary Search Tree","contentType":"directory"},{"name":"Binary Search","path":"Binary Search","contentType":"directory"},{"name":"Binary Tree","path":"Binary Tree","contentType":"directory"},{"name":"Bit Set","path":"Bit Set","contentType":"directory"},{"name":"Bloom Filter","path":"Bloom Filter","contentType":"directory"},{"name":"Bounded Priority Queue","path":"Bounded Priority Queue","contentType":"directory"},{"name":"Boyer-Moore-Horspool","path":"Boyer-Moore-Horspool","contentType":"directory"},{"name":"Breadth-First Search","path":"Breadth-First Search","contentType":"directory"},{"name":"Brute-Force String Search","path":"Brute-Force String Search","contentType":"directory"},{"name":"Bubble Sort","path":"Bubble Sort","contentType":"directory"},{"name":"Bucket Sort","path":"Bucket Sort","contentType":"directory"},{"name":"Closest Pair","path":"Closest Pair","contentType":"directory"},{"name":"Comb Sort","path":"Comb Sort","contentType":"directory"},{"name":"Combinatorics","path":"Combinatorics","contentType":"directory"},{"name":"Convex Hull","path":"Convex Hull","contentType":"directory"},{"name":"Count Occurrences","path":"Count Occurrences","contentType":"directory"},{"name":"Counting Sort","path":"Counting Sort","contentType":"directory"},{"name":"Depth-First Search","path":"Depth-First Search","contentType":"directory"},{"name":"Deque","path":"Deque","contentType":"directory"},{"name":"Dijkstra Algorithm","path":"Dijkstra Algorithm","contentType":"directory"},{"name":"DiningPhilosophers","path":"DiningPhilosophers","contentType":"directory"},{"name":"Egg Drop Problem","path":"Egg Drop Problem","contentType":"directory"},{"name":"Encode and Decode Tree","path":"Encode and Decode Tree","contentType":"directory"},{"name":"Fixed Size Array","path":"Fixed Size Array","contentType":"directory"},{"name":"Fizz Buzz","path":"Fizz Buzz","contentType":"directory"},{"name":"GCD","path":"GCD","contentType":"directory"},{"name":"Genetic","path":"Genetic","contentType":"directory"},{"name":"Graph","path":"Graph","contentType":"directory"},{"name":"Hash Set","path":"Hash Set","contentType":"directory"},{"name":"Hash Table","path":"Hash Table","contentType":"directory"},{"name":"Hashed Heap","path":"Hashed Heap","contentType":"directory"},{"name":"HaversineDistance","path":"HaversineDistance","contentType":"directory"},{"name":"Heap Sort","path":"Heap Sort","contentType":"directory"},{"name":"Heap","path":"Heap","contentType":"directory"},{"name":"Huffman Coding","path":"Huffman Coding","contentType":"directory"},{"name":"Images","path":"Images","contentType":"directory"},{"name":"Insertion Sort","path":"Insertion Sort","contentType":"directory"},{"name":"Introsort","path":"Introsort","contentType":"directory"},{"name":"K-Means","path":"K-Means","contentType":"directory"},{"name":"Karatsuba Multiplication","path":"Karatsuba Multiplication","contentType":"directory"},{"name":"Knuth-Morris-Pratt","path":"Knuth-Morris-Pratt","contentType":"directory"},{"name":"Kth Largest Element","path":"Kth Largest Element","contentType":"directory"},{"name":"LRU Cache","path":"LRU Cache","contentType":"directory"},{"name":"Linear Regression","path":"Linear Regression","contentType":"directory"},{"name":"Linear Search","path":"Linear Search","contentType":"directory"},{"name":"Linked List","path":"Linked List","contentType":"directory"},{"name":"Longest Common Subse
41D7
quence","path":"Longest Common Subsequence","contentType":"directory"},{"name":"Merge Sort","path":"Merge Sort","contentType":"directory"},{"name":"Miller-Rabin Primality Test","path":"Miller-Rabin Primality Test","contentType":"directory"},{"name":"Minimum Edit Distance","path":"Minimum Edit Distance","contentType":"directory"},{"name":"Minimum Spanning Tree (Unweighted)","path":"Minimum Spanning Tree (Unweighted)","contentType":"directory"},{"name":"Minimum Spanning Tree","path":"Minimum Spanning Tree","contentType":"directory"},{"name":"MinimumCoinChange","path":"MinimumCoinChange","contentType":"directory"},{"name":"Monty Hall Problem","path":"Monty Hall Problem","contentType":"directory"},{"name":"Multiset","path":"Multiset","contentType":"directory"},{"name":"Myers Difference Algorithm","path":"Myers Difference Algorithm","contentType":"directory"},{"name":"Naive Bayes Classifier","path":"Naive Bayes Classifier","contentType":"directory"},{"name":"Octree","path":"Octree","contentType":"directory"},{"name":"Ordered Array","path":"Ordered Array","contentType":"directory"},{"name":"Ordered Set","path":"Ordered Set","contentType":"directory"},{"name":"Palindromes","path":"Palindromes","contentType":"directory"},{"name":"Points Lines Planes","path":"Points Lines Planes","contentType":"directory"},{"name":"Priority Queue","path":"Priority Queue","contentType":"directory"},{"name":"QuadTree","path":"QuadTree","contentType":"directory"},{"name":"Queue","path":"Queue","contentType":"directory"},{"name":"Quicksort","path":"Quicksort","contentType":"directory"},{"name":"Rabin-Karp","path":"Rabin-Karp","contentType":"directory"},{"name":"Radix Sort","path":"Radix Sort","contentType":"directory"},{"name":"Radix Tree","path":"Radix Tree","contentType":"directory"},{"name":"Red-Black Tree","path":"Red-Black Tree","contentType":"directory"},{"name":"Ring Buffer","path":"Ring Buffer","contentType":"directory"},{"name":"Rootish Array Stack","path":"Rootish Array Stack","contentType":"directory"},{"name":"Run-Length Encoding","path":"Run-Length Encoding","contentType":"directory"},{"name":"Segment Tree","path":"Segment Tree","contentType":"directory"},{"name":"Select Minimum Maximum","path":"Select Minimum Maximum","contentType":"directory"},{"name":"Selection Sampling","path":"Selection Sampling","contentType":"directory"},{"name":"Selection Sort","path":"Selection Sort","contentType":"directory"},{"name":"Set Cover (Unweighted)","path":"Set Cover (Unweighted)","contentType":"directory"},{"name":"Shell Sort","path":"Shell Sort","contentType":"directory"},{"name":"Shortest Path (Unweighted)","path":"Shortest Path (Unweighted)","contentType":"directory"},{"name":"Shuffle","path":"Shuffle","contentType":"directory"},{"name":"Shunting Yard","path":"Shunting Yard","contentType":"directory"},{"name":"Simulated annealing","path":"Simulated annealing","contentType":"directory"},{"name":"Single-Source Shortest Paths (Weighted)","path":"Single-Source Shortest Paths (Weighted)","contentType":"directory"},{"name":"Singly Linked List","path":"Singly Linked List","contentType":"directory"},{"name":"Skip-List","path":"Skip-List","contentType":"directory"},{"name":"Slow Sort","path":"Slow Sort","contentType":"directory"},{"name":"Sorted Set","path":"Sorted Set","contentType":"directory"},{"name":"Sparse Table","path":"Sparse Table","contentType":"directory"},{"name":"Splay Tree","path":"Splay Tree","contentType":"directory"},{"name":"Stack","path":"Stack","contentType":"directory"},{"name":"Strassen Matrix Multiplication","path":"Strassen Matrix Multiplication","contentType":"directory"},{"name":"Ternary Search Tree","path":"Ternary Search Tree","contentType":"directory"},{"name":"Threaded Binary Tree","path":"Threaded Binary Tree","contentType":"directory"},{"name":"Topological Sort","path":"Topological Sort","contentType":"directory"},{"name":"Treap","path":"Treap","contentType":"directory"},{"name":"Tree","path":"Tree","contentType":"directory"},{"name":"Trie","path":"Trie","contentType":"directory"},{"name":"Two-Sum Problem","path":"Two-Sum Problem","contentType":"directory"},{"name":"Union-Find","path":"Union-Find","contentType":"directory"},{"name":"Z-Algorithm","path":"Z-Algorithm","contentType":"directory"},{"name":".gitignore","path":".gitignore","contentType":"file"},{"name":".swiftlint.yml","path":".swiftlint.yml","contentType":"file"},{"name":"Algorithm Design.markdown","path":"Algorithm Design.markdown","contentType":"file"},{"name":"Big-O Notation.markdown","path":"Big-O Notation.markdown","contentType":"file"},{"name":"LICENSE.txt","path":"LICENSE.txt","contentType":"file"},{"name":"README.markdown","path":"README.markdown","contentType":"file"},{"name":"Under Construction.markdown","path":"Under Construction.markdown","contentType":"file"},{"name":"What are Algorithms.markdown","path":"What are Algorithms.markdown","contentType":"file"},{"name":"Why Algorithms.markdown","path":"Why Algorithms.markdown","contentType":"file"},{"name":"gfm-render.sh","path":"gfm-render.sh","contentType":"file"},{"name":"install_swiftlint.sh","path":"install_swiftlint.sh","contentType":"file"}],"totalCount":118}},"fileTreeProcessingTime":5.190163,"foldersToFetch":[],"treeExpanded":true,"symbolsExpanded":false,"csrf_tokens":{"/phantomato/swift-algorithm-club/branches":{"post":"6kmWR6t7noLAMAC54Jjk4aUuhBB85MPQVJXVXyOo8ajWmnOg2THiE7uNLYoZUp2avRjRgSLCzduNH1TWA4_WyQ"},"/phantomato/swift-algorithm-club/branches/fetch_and_merge/master":{"post":"Azha-tNxxyVqT_nNsXuoEV7YF-qMyBGhtz7DCqLq4lYKvH8zXT3nssWLbzB4qC2L6Tq_tC-QOcawp3unegGMYw"},"/phantomato/swift-algorithm-club/branches/fetch_and_merge/master?discard_changes=true":{"post":"76Fjp8BsABfgSrj9gXjcJL7hYkGfM4MZGKN4n4a5nY7mJUZuTiAggE-OLgBIq1m-CQPKHzxrq34fOsAyXlLzuw"}}},"title":"swift-algorithm-club/Sparse Table at master · phantomato/swift-algorithm-club","appPayload":{"helpUrl":"https://docs.github.com","findFileWorkerPath":"/assets-cdn/worker/find-file-worker-263cab1760dd.js","findInFileWorkerPath":"/assets-cdn/worker/find-in-file-worker-1b17b3e7786a.js","githubDevUrl":null,"enabled_features":{"code_nav_ui_events":false,"react_blob_overlay":false,"accessible_code_button":true}}}