{"id":22959,"date":"2022-11-22T17:20:25","date_gmt":"2022-11-22T11:50:25","guid":{"rendered":"https:\/\/jassweb.com\/solved\/solved-data-structure-and-algorithm-for-max-min-apple-number-search-and-update-closed\/"},"modified":"2022-11-22T17:20:25","modified_gmt":"2022-11-22T11:50:25","slug":"solved-data-structure-and-algorithm-for-max-min-apple-number-search-and-update-closed","status":"publish","type":"post","link":"https:\/\/jassweb.com\/solved\/solved-data-structure-and-algorithm-for-max-min-apple-number-search-and-update-closed\/","title":{"rendered":"[Solved] Data structure and algorithm for Max\/Min apple number search and update [closed]"},"content":{"rendered":"

[ad_1]
\n<\/p>\n

\n
\n
<\/div>\n
\n
\n

You can impose a tree structure on an array. The leaves of the tree are the array itself. The next level up has one node for each pair of array elements. The next level up has four descendants for each node, and so on… <\/p>\n<\/p>\n

\n       15
\n   13      14\n 9   10  11  12\n1 2  3 4 5 6 7 8\n<\/pre>\n
Here 1..8 might be the original data points, and the higher numbers show tree nodes that you can add. Now if you hold at each internal node the minimum and maximum value found amongst any of its descendants you will find the minimum and maximum value for the whole array at the root of the tree, and you can find the index involved by tracking down the tree to it, or by storing indexes as well as values. When you update a value at the leaves, you track up the tree, if necessary, to recalculate the minimum and maximum values stored at its parents. All of these actions take time O(log n) because that is the height of the tree.<\/p>\n
As an example, suppose that the input data is 101..108. This will produce the following tree of maximum values, with the absolute maximum for the whole tree at the top:<\/p>\n
\n\n                 108\n       104                  108\n  102        104       106       108\n101  102  103  104  105  106  107  108\n<\/pre>\n
If you now change the value 104 to 109, you can see that you need only change the values up from here to the top of the tree to restore the invariants of the datastructure and get the new maximum at the top<\/p>\n
\n\n                 109\n       109                  108\n  102        109       106       108\n101  102  103  109  105  106  107  108\n<\/pre>\n<\/p><\/div>\n
<\/div>\n<\/div>\n
            5<\/span> <\/p><\/div>\n<\/div>\n
[ad_2]<\/p>\n
solved Data structure and algorithm for Max\/Min apple number search and update [closed] <\/p>\n","protected":false},"excerpt":{"rendered":"
[ad_1] You can impose a tree structure on an array. The leaves of the tree are the array itself. The next level up has one node for each pair of array elements. The next level up has four descendants for each node, and so on… 15 13 14 9 10 11 12 1 2 3 … Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[320],"tags":[457,859],"class_list":["post-22959","post","type-post","status-publish","format-standard","hentry","category-solved","tag-algorithm","tag-data-structures"],"yoast_head":"\n[Solved] Data structure and algorithm for Max\/Min apple number search and update [closed] - JassWeb<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/jassweb.com\/solved\/solved-data-structure-and-algorithm-for-max-min-apple-number-search-and-update-closed\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"[Solved] Data structure and algorithm for Max\/Min apple number search and update [closed] - JassWeb\" \/>\n<meta property=\"og:description\" content=\"[ad_1] You can impose a tree structure on an array. The leaves of the tree are the array itself. The next level up has one node for each pair of array elements. The next level up has four descendants for each node, and so on… 15 13 14 9 10 11 12 1 2 3 ... Read more\" \/>\n<meta property=\"og:url\" content=\"https:\/\/jassweb.com\/solved\/solved-data-structure-and-algorithm-for-max-min-apple-number-search-and-update-closed\/\" \/>\n<meta property=\"og:site_name\" content=\"JassWeb\" \/>\n<meta property=\"article:published_time\" content=\"2022-11-22T11:50:25+00:00\" \/>\n<meta name=\"author\" content=\"Kirat\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Kirat\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-data-structure-and-algorithm-for-max-min-apple-number-search-and-update-closed\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-data-structure-and-algorithm-for-max-min-apple-number-search-and-update-closed\/\"},\"author\":{\"name\":\"Kirat\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\"},\"headline\":\"[Solved] Data structure and algorithm for Max\/Min apple number search and update [closed]\",\"datePublished\":\"2022-11-22T11:50:25+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-data-structure-and-algorithm-for-max-min-apple-number-search-and-update-closed\/\"},\"wordCount\":264,\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"keywords\":[\"algorithm\",\"data-structures\"],\"articleSection\":[\"Solved\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-data-structure-and-algorithm-for-max-min-apple-number-search-and-update-closed\/\",\"url\":\"https:\/\/jassweb.com\/solved\/solved-data-structure-and-algorithm-for-max-min-apple-number-search-and-update-closed\/\",\"name\":\"[Solved] Data structure and algorithm for Max\/Min apple number search and update [closed] - JassWeb\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#website\"},\"datePublished\":\"2022-11-22T11:50:25+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-data-structure-and-algorithm-for-max-min-apple-number-search-and-update-closed\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/jassweb.com\/solved\/solved-data-structure-and-algorithm-for-max-min-apple-number-search-and-update-closed\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-data-structure-and-algorithm-for-max-min-apple-number-search-and-update-closed\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/jassweb.com\/solved\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"[Solved] Data structure and algorithm for Max\/Min apple number search and update [closed]\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/jassweb.com\/solved\/#website\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"name\":\"JassWeb\",\"description\":\"Build High-quality Websites\",\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/jassweb.com\/solved\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\",\"name\":\"Jass Web\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"contentUrl\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"width\":693,\"height\":132,\"caption\":\"Jass Web\"},\"image\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\"}},{\"@type\":\"Person\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\",\"name\":\"Kirat\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775798750\",\"contentUrl\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775798750\",\"caption\":\"Kirat\"},\"sameAs\":[\"http:\/\/jassweb.com\"],\"url\":\"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"[Solved] Data structure and algorithm for Max\/Min apple number search and update [closed] - JassWeb","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/jassweb.com\/solved\/solved-data-structure-and-algorithm-for-max-min-apple-number-search-and-update-closed\/","og_locale":"en_US","og_type":"article","og_title":"[Solved] Data structure and algorithm for Max\/Min apple number search and update [closed] - JassWeb","og_description":"[ad_1] You can impose a tree structure on an array. The leaves of the tree are the array itself. The next level up has one node for each pair of array elements. The next level up has four descendants for each node, and so on… 15 13 14 9 10 11 12 1 2 3 ... Read more","og_url":"https:\/\/jassweb.com\/solved\/solved-data-structure-and-algorithm-for-max-min-apple-number-search-and-update-closed\/","og_site_name":"JassWeb","article_published_time":"2022-11-22T11:50:25+00:00","author":"Kirat","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Kirat","Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/jassweb.com\/solved\/solved-data-structure-and-algorithm-for-max-min-apple-number-search-and-update-closed\/#article","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/solved-data-structure-and-algorithm-for-max-min-apple-number-search-and-update-closed\/"},"author":{"name":"Kirat","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31"},"headline":"[Solved] Data structure and algorithm for Max\/Min apple number search and update [closed]","datePublished":"2022-11-22T11:50:25+00:00","mainEntityOfPage":{"@id":"https:\/\/jassweb.com\/solved\/solved-data-structure-and-algorithm-for-max-min-apple-number-search-and-update-closed\/"},"wordCount":264,"publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"keywords":["algorithm","data-structures"],"articleSection":["Solved"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/jassweb.com\/solved\/solved-data-structure-and-algorithm-for-max-min-apple-number-search-and-update-closed\/","url":"https:\/\/jassweb.com\/solved\/solved-data-structure-and-algorithm-for-max-min-apple-number-search-and-update-closed\/","name":"[Solved] Data structure and algorithm for Max\/Min apple number search and update [closed] - JassWeb","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/#website"},"datePublished":"2022-11-22T11:50:25+00:00","breadcrumb":{"@id":"https:\/\/jassweb.com\/solved\/solved-data-structure-and-algorithm-for-max-min-apple-number-search-and-update-closed\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/jassweb.com\/solved\/solved-data-structure-and-algorithm-for-max-min-apple-number-search-and-update-closed\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/jassweb.com\/solved\/solved-data-structure-and-algorithm-for-max-min-apple-number-search-and-update-closed\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/jassweb.com\/solved\/"},{"@type":"ListItem","position":2,"name":"[Solved] Data structure and algorithm for Max\/Min apple number search and update [closed]"}]},{"@type":"WebSite","@id":"https:\/\/jassweb.com\/solved\/#website","url":"https:\/\/jassweb.com\/solved\/","name":"JassWeb","description":"Build High-quality Websites","publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/jassweb.com\/solved\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/jassweb.com\/solved\/#organization","name":"Jass Web","url":"https:\/\/jassweb.com\/solved\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/","url":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","contentUrl":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","width":693,"height":132,"caption":"Jass Web"},"image":{"@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/"}},{"@type":"Person","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31","name":"Kirat","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/","url":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775798750","contentUrl":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775798750","caption":"Kirat"},"sameAs":["http:\/\/jassweb.com"],"url":"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/"}]}},"_links":{"self":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/22959","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/comments?post=22959"}],"version-history":[{"count":0,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/22959\/revisions"}],"wp:attachment":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/media?parent=22959"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/categories?post=22959"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/tags?post=22959"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}