8000 javascript-algorithms/src/data-structures/tree/segment-tree at merge · paulepps/javascript-algorithms · GitHub
[go: up one dir, main page]
Skip to content
< 63D8 script type="application/json" data-target="react-app.embeddedData">{"payload":{"allShortcutsEnabled":false,"path":"src/data-structures/tree/segment-tree","repo":{"id":354186905,"defaultBranch":"master","name":"javascript-algorithms","ownerLogin":"paulepps","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2021-04-03T03:08:08.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/1527399?v=4","public":true,"private":false,"isOrgOwned":false},"currentUser":null,"refInfo":{"name":"merge","listCacheKey":"v0:1617419289.309967","canEdit":false,"refType":"branch","currentOid":"83357075c4698f487af733e6e0bf9567ba94c266"},"tree":{"items":[{"name":"__test__","path":"src/data-structures/tree/segment-tree/__test__","contentType":"directory"},{"name":"README.md","path":"src/data-structures/tree/segment-tree/README.md","contentType":"file"},{"name":"README.pt-BR.md","path":"src/data-structures/tree/segment-tree/README.pt-BR.md","contentType":"file"},{"name":"SegmentTree.js","path":"src/data-structures/tree/segment-tree/SegmentTree.js","contentType":"file"}],"templateDirectorySuggestionUrl":null,"readme":{"displayName":"README.md","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\"\u003eSegment Tree\u003c/h1\u003e\u003ca id=\"user-content-segment-tree\" class=\"anchor\" aria-label=\"Permalink: Segment Tree\" href=\"#segment-tree\"\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\"\u003e\u003cem\u003eRead this in other languages:\u003c/em\u003e\n\u003ca href=\"/paulepps/javascript-algorithms/blob/merge/src/data-structures/tree/segment-tree/README.pt-BR.md\"\u003e\u003cem\u003ePortuguês\u003c/em\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eIn computer science, a \u003cstrong\u003esegment tree\u003c/strong\u003e also known as a statistic tree\nis a tree data structure used for storing information about intervals,\nor segments. It allows querying which of the stored segments contain\na given point. It is, in principle, a static structure; that is,\nit's a structure that cannot be modified once it's built. A similar\ndata structure is the interval tree.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eA segment tree is a binary tree. The root of the tree represents the\nwhole array. The two children of the root represent the\nfirst and second halves of the array. Similarly, the\nchildren of each node corresponds to the two halves of\nthe array corresponding to the node.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eWe build the tree bottom up, with the value of each node\nbeing the \"minimum\" (or any other function) of its children's values. This will\ntake \u003ccode\u003eO(n log n)\u003c/code\u003e time. The number\nof operations done is the height of the tree, which\nis \u003ccode\u003eO(log n)\u003c/code\u003e. To do range queries, each node splits the\nquery into two parts, one sub-query for each child.\nIf a query contains the whole subarray of a node, we\ncan use the precomputed value at the node. Using this\noptimisation, we can prove that only \u003ccode\u003eO(log n)\u003c/code\u003e minimum\noperations are done.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer nofollow\" href=\"https://camo.githubusercontent.com/53ff46f5c25242f72c301a7adf94c32c5b3799ca1385089a22e648eb39e70beb/68747470733a2f2f7777772e6765656b73666f726765656b732e6f72672f77702d636f6e74656e742f75706c6f6164732f52616e67654d696e696d756d51756572792e706e67\"\u003e\u003cimg src=\"https://camo.githubusercontent.com/53ff46f5c25242f72c301a7adf94c32c5b3799ca1385089a22e648eb39e70beb/68747470733a2f2f7777772e6765656b73666f726765656b732e6f72672f77702d636f6e74656e742f75706c6f6164732f52616e67654d696e696d756d51756572792e706e67\" alt=\"Min Segment Tree\" data-canonical-src=\"https://www.geeksforgeeks.org/wp-content/uploads/RangeMinimumQuery.png\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer nofollow\" href=\"https://camo.githubusercontent.com/89d1e98e64f6de9ac0307c88044da3ed52c4de25a7bfe207ac22785879c59626/68747470733a2f2f7777772e6765656b73666f726765656b732e6f72672f77702d636f6e74656e742f75706c6f6164732f7365676d656e742d74726565312e706e67\"\u003e\u003cimg src=\"https://camo.githubusercontent.com/89d1e98e64f6de9ac0307c88044da3ed52c4de25a7bfe207ac22785879c59626/68747470733a2f2f7777772e6765656b73666f726765656b732e6f72672f77702d636f6e74656e742f75706c6f6164732f7365676d656e742d74726565312e706e67\" alt=\"Sum Segment Tree\" data-canonical-src=\"https://www.geeksforgeeks.org/wp-content/uploads/segment-tree1.png\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eApplication\u003c/h2\u003e\u003ca id=\"user-content-application\" class=\"anchor\" aria-label=\"Permalink: Application\" href=\"#application\"\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\"\u003eA segment tree is a data structure designed to perform\ncertain array operations efficiently - especially those\ninvolving range queries.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eApplications of the segment tree are in the areas of computational geometry,\nand geographic information systems.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eCurrent implementation of Segment Tree implies that you may\npass any binary (with two input params) function to it and\nthus you're able to do range query for variety of functions.\nIn tests you may find examples of doing \u003ccode\u003emin\u003c/code\u003e, \u003ccode\u003emax\u003c/code\u003e and \u003ccode\u003esum\u003c/code\u003e range\nqueries on SegmentTree.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eReferences\u003c/h2\u003e\u003ca id=\"user-content-references\" class=\"anchor\" aria-label=\"Permalink: References\" href=\"#references\"\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://en.wikipedia.org/wiki/Segment_tree\" rel=\"nofollow\"\u003eWikipedia\u003c/a\u003e\u003c/li\u003e\n\u003cli\u003e\u003ca href=\"https://www.youtube.com/watch?v=ZBHKZF5w4YU\u0026amp;index=65\u0026amp;list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8\" rel=\"nofollow\"\u003eYouTube\u003c/a\u003e\u003c/li\u003e\n\u003cli\u003e\u003ca href=\"https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/\" rel=\"nofollow\"\u003eGeeksForGeeks\u003c/a\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/article\u003e","errorMessage":null,"headerInfo":{"toc":[{"level":1,"text":"Segment Tree","anchor":"segment-tree","htmlText":"Segment Tree"},{"level":2,"text":"Application","anchor":"application","htmlText":"Application"},{"level":2,"text":"References","anchor":"references","htmlText":"References"}],"siteNavLoginPath":"/login?return_to=https%3A%2F%2Fgithub.com%2Fpaulepps%2Fjavascript-algorithms%2Ftree%2Fmerge%2Fsrc%2Fdata-structures%2Ftree%2Fsegment-tree"}},"totalCount":4,"showBranchInfobar":true},"fileTree":{"src/data-structures/tree":{"items":[{"name":"__test__","path":"src/data-structures/tree/__test__","contentType":"directory"},{"name":"avl-tree","path":"src/data-structures/tree/avl-tree","contentType":"directory"},{"name":"binary-search-tree","path":"src/data-structures/tree/binary-search-tree","contentType":"directory"},{"name":"fenwick-tree","path":"src/data-structures/tree/fenwick-tree","contentType":"directory"},{"name":"red-black-tree","path":"src/data-structures/tree/red-black-tree","contentType":"directory"},{"name":"segment-tree","path":"src/data-structures/tree/segment-tree","contentType":"directory"},{"name":"BinaryTreeNode.js","path":"src/data-structures/tree/BinaryTreeNode.js","contentType":"file"},{"name":"README.md","path":"src/data-structures/tree/README.md","contentType":"file"},{"name":"README.pt-BR.md","path":"src/data-structures/tree/README.pt-BR.md","contentType":"file"},{"name":"README.zh-CN.md","path":"src/data-structures/tree/README.zh-CN.md","contentType":"file"}],"totalCount":10},"src/data-structures":{"items":[{"name":"bloom-filter","path":"src/data-structures/bloom-filter","contentType":"directory"},{"name":"disjoint-set","path":"src/data-structures/disjoint-set","contentType":"directory"},{"name":"doubly-linked-list","path":"src/data-structures/doubly-linked-list","contentType":"directory"},{"name":"graph","path":"src/data-structures/graph","contentType":"directory"},{"name":"hash-table","path":"src/data-structures/hash-table","contentType":"directory"},{"name":"heap","path":"src/data-structures/heap","contentType":"directory"},{"name":"linked-list","path":"src/data-structures/linked-list","contentType":"directory"},{"name":"priority-queue","path":"src/data-structures/priority-queue","contentType":"directory"},{"name":"queue","path":"src/data-structures/queue","contentType":"directory"},{"name":"stack","path":"src/data-structures/stack","contentType":"directory"},{"name":"tree","path":"src/data-structures/tree","contentType":"directory"},{"name":"trie","path":"src/data-structures/trie","contentType":"directory"}],"totalCount":12},"src":{"items":[{"name":"algorithms","path":"src/algorithms","contentType":"directory"},{"name":"data-structures","path":"src/data-structures","contentType":"directory"},{"name":"playground","path":"src/playground","contentType":"directory"},{"name":"utils","path":"src/utils","contentType":"directory"}],"totalCount":4},"":{"items":[{"name":".github","path":".github","contentType":"directory"},{"name":"assets","path":"assets","contentType":"directory"},{"name":"src","path":"src","contentType":"directory"},{"name":".babelrc","path":".babelrc","contentType":"file"},{"name":".editorconfig","path":".editorconfig","contentType":"file"},{"name":".eslintrc","path":".eslintrc","contentType":"file"},{"name":".gitignore","path":".gitignore","contentType":"file"},{"name":".huskyrc.json","path":".huskyrc.json","contentType":"file"},{"name":"BACKERS.md","path":"BACKERS.md","contentType":"file"},{"name":"CODE_OF_CONDUCT.md","path":"CODE_OF_CONDUCT.md","contentType":"file"},{"name":"CONTRIBUTING.md","path":"CONTRIBUTING.md","contentType":"file"},{"name":"LICENSE","path":"LICENSE","contentType":"file"},{"name":"README.ar-AR.md","path":"README.ar-AR.md","contentType":"file"},{"name":"README.es-ES.md","path":"README.es-ES.md","contentType":"file"},{"name":"README.fr-FR.md","path":"README.fr-FR.md","contentType":"file"},{"name":"README.id-ID.md","path":"README.id-ID.md","contentType":"file"},{"name":"README.it-IT.md","path":"README.it-IT.md","contentType":"file"},{"name":"README.ja-JP.md","path":"README.ja-JP.md","contentType":"file"},{"name":"README.ko-KR.md","path":"README.ko-KR.md","contentType":"file"},{"name":"README.md","path":"README.md","contentType":"file"},{"name":"README.pl-PL.md","path":"README.pl-PL.md","contentType":"file"},{"name":"README.pt-BR.md","path":"README.pt-BR.md","contentType":"file"},{"name":"README.ru-RU.md","path":"README.ru-RU.md","contentType":"file"},{"name":"README.tr-TR.md","path":"README.tr-TR.md","contentType":"file"},{"name":"README.uk-UA.md","path":"README.uk-UA.md","contentType":"file"},{"name":"README.zh-CN.md","path":"README.zh-CN.md","contentType":"file"},{"name":"README.zh-TW.md","path":"README.zh-TW.md","contentType":"file"},{"name":"jest.config.js","path":"jest.config.js","contentType":"file"},{"name":"package-lock.json","path":"package-lock.json","contentType":"file"},{"name":"package.json","path":"package.json","contentType":"file"}],"totalCount":30}},"fileTreeProcessingTime":14.053778,"foldersToFetch":[],"treeExpanded":true,"symbolsExpanded":false,"csrf_tokens":{"/paulepps/javascript-algorithms/branches":{"post":"e9YbN7gBXlfgnkmwnMER3XARzulvtQKWo2qxgUoenbUgwetuzs3cDecfRvI_AiLQNG3YH8xubvc266bLU-SRNA"},"/paulepps/javascript-algorithms/branches/fetch_and_merge/merge":{"post":"q4RNwNvXs_LEkG5ARsh09RM8TAqmXUhCmqW87a05bvjI7ENcVQqjhciyxjkjsXN6K6k5_zF5u8Ds9Ap2qk4cNw"},"/paulepps/javascript-algorithms/branches/fetch_and_merge/merge?discard_changes=true":{"post":"Bxb-Hv2C-OS25YZf2ropqA7A00r92H8JdgsKlGDenJpkfvCCc1_ok7rHLia_wy4nNlWmv2r8jIsAWrwPZ6nuVQ"}}},"title":"javascript-algorithms/src/data-structures/tree/segment-tree at merge · paulepps/javascript-algorithms","appPayload":{"helpUrl":"https://docs.github.com","findFileWorkerPath":"/assets-cdn/worker/find-file-worker-263cab1760dd.js","findInFileWorkerPath":"/assets-cdn/worker/find-in-file-worker-98e6e9db3609.js","githubDevUrl":null,"enabled_features":{"code_nav_ui_events":false,"react_blob_overlay":false,"accessible_code_button":true}}}
0