{"id":411,"date":"2015-11-29T16:35:55","date_gmt":"2015-11-29T13:35:55","guid":{"rendered":"http:\/\/java.mazurok.com\/?p=411"},"modified":"2016-06-29T18:12:58","modified_gmt":"2016-06-29T15:12:58","slug":"bitsegmentedarray-by-tolia","status":"publish","type":"post","link":"https:\/\/java.mazurok.com\/?p=411","title":{"rendered":"BigSegmentedArray by Tolia"},"content":{"rendered":"<p>\u041c\u043d\u0435 \u043f\u0440\u0435\u0434\u043e\u0441\u0442\u0430\u0432\u0438\u043b\u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043a\u043b\u0430\u0441\u0441, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0430\u0441\u043b\u0435\u0434\u0443\u0435\u0442 SegmentedArray \u0438 \u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u0438\u0437\u0443\u0435\u0442\u0441\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c:<\/p>\n<ul>\n<li>\u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u043c\u0430\u0441\u0441\u0438\u0432<\/li>\n<li>\u0447\u0430\u0441\u0442\u044b\u0435 \u0437\u0430\u043f\u0440\u043e\u0441\u044b get(), min();<\/li>\n<\/ul>\n<p>\u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043a\u043e\u043c\u0430\u043d\u0434\u0430 set\u00a0\u0437\u0430\u0434\u0430\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043d\u0430 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u0435, \u044f \u0440\u0435\u0448\u0438\u043b \u0441\u0434\u0435\u043b\u0430\u0442\u044c &#171;\u0434\u0435\u0440\u0435\u0432\u043e \u043e\u0442\u0440\u0435\u0437\u043a\u043e\u0432&#187;. \u041a\u043e\u0442\u043e\u0440\u043e\u0435 \u0443\u0441\u0442\u0440\u043e\u0435\u043d\u043e \u043a\u0430\u043a \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0430 (\u0432 \u0437\u0430\u0434\u0430\u043d\u0438\u0438 \u0431\u043e\u043b\u044c\u0448\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0437\u0430\u043f\u0440\u043e\u0441\u043e\u0432 get(), \u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0438\u0441\u043a\u0430\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443), \u0438\u043c\u0435\u044f \u0432 \u0441\u0435\u0431\u0435 \u043b\u0435\u0432\u044b\u0439 \u0438 \u043f\u0440\u0430\u0432\u044b\u0435 \u043a\u043e\u043d\u0446\u044b \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u0430, \u0430 \u0442\u0430\u043a\u0436\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043d\u0430 \u044d\u0442\u043e\u043c \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u0435.<\/p>\n<p>\u041e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u0432 \u0434\u0430\u043d\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435 &#8212; set(). \u0418 \u043e\u043d\u0430 \u0441\u0430\u043c\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u0430\u044f \u043f\u043e \u0441\u0432\u043e\u0435\u0439 \u0441\u0445\u0435\u043c\u0435. \u041a\u043e\u0433\u0434\u0430 \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u0442\u044c \u0437\u0430\u043f\u0440\u043e\u0441 \u043d\u0430 \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043d\u0430 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u0435, \u043d\u0430\u0434\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u0443\u0437\u0435\u043b \u043f\u0443\u0441\u0442, \u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0442\u0430\u043a\u043e\u0433\u043e \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u0430 \u0435\u0449\u0435 \u043d\u0435 \u0437\u0430\u0434\u0430\u0432\u0430\u043b\u0438, \u0438 \u0442\u043e\u0433\u0434\u0430 \u043c\u043e\u0436\u043d\u043e \u0435\u0433\u043e \u0441\u043e\u0437\u0434\u0430\u0442\u044c. \u0415\u0441\u043b\u0438 \u0436\u0435 \u0443\u0437\u0435\u043b \u043d\u0435 \u043f\u0443\u0441\u0442, \u0442\u043e \u043d\u0430\u0434\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u0432 \u0434\u0430\u043d\u043d\u043e\u043c \u0443\u0437\u043b\u0435 \u043b\u0438 \u0437\u0430\u0434\u0430\u0435\u0442\u0441\u044f \u043d\u0430\u0448 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b, \u0438\u043b\u0438 \u0436\u0435 \u043d\u0430\u0434\u043e \u043f\u0435\u0440\u0435\u0439\u0442\u0438 \u043a \u0434\u0440\u0443\u0433\u043e\u043c\u0443. \u0415\u0441\u043b\u0438 \u0436\u0435 \u0432 \u0434\u0430\u043d\u043d\u043e\u043c \u0443\u0437\u043b\u0435 \u043d\u0430\u0434\u043e \u0437\u0430\u0434\u0430\u0442\u044c \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b, \u0442\u043e \u0443 \u043d\u0430\u0441 \u0432\u044b\u0440\u0438\u0441\u043e\u0432\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0442\u0440\u0438 \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u0438: \u043a\u043e\u0433\u0434\u0430 \u0437\u0430\u0434\u0430\u0432\u0430\u0435\u043c\u044b\u0439 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b \u043d\u0435 \u043f\u0440\u0435\u0432\u043e\u0441\u0445\u043e\u0434\u0438\u0442\u00a0\u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u0430 \u0443\u0437\u043b\u0430, \u043a\u043e\u0433\u0434\u0430 \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u0439 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b \u043f\u0440\u0435\u0432\u043e\u0441\u0445\u043e\u0434\u0438\u0442\u044c \u00a0\u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b \u0443\u0437\u043b\u0430 \u0438 \u043a\u043e\u0433\u0434\u0430 \u043e\u0434\u043d\u0430 \u0442\u043e\u0447\u043a\u0430 \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u0430 \u043b\u0435\u0436\u0438\u0442 \u0432\u043d\u0443\u0442\u0440\u0438 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u0430 \u0443\u0437\u043b\u0430, \u0430 \u0434\u0440\u0443\u0433\u0430\u044f, \u0432\u043d\u0435 \u0435\u0433\u043e. \u0412 \u043f\u0435\u0440\u0432\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435\u043c, \u043f\u0440\u043e\u0441\u0442\u043e \u0440\u0430\u0437\u0431\u0438\u0432\u0430\u0435\u043c \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0438\u0439 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b \u043d\u0430 \u0442\u0440\u0438 \u043f\u043e\u0434\u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u0430: \u043b\u0435\u0432\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0435\u0433\u043e \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u0430, \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u0439 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b \u0438 \u043f\u0440\u0430\u0432\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0435\u0433\u043e \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u0430. \u0412\u043e-\u0432\u0442\u043e\u0440\u043e\u043c, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0442\u044c \u0433\u0440\u0430\u043d\u0438\u0446\u044b \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0435\u0433\u043e \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u0430 \u0434\u043e \u0437\u0430\u0434\u0430\u0432\u0430\u0435\u043c\u043e\u0433\u043e, \u0438 \u0443\u0434\u0430\u043b\u0438\u0442\u044c \u0432\u0441\u0435 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u044b(\u0432 \u043b\u0435\u0432\u043e\u043c \u0438 \u043f\u0440\u0430\u0432\u043e\u043c \u0443\u0437\u043b\u0430\u0445), \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0439 \u043d\u043e\u0432\u044b\u0439 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b \u043f\u0435\u0440\u0435\u043a\u0440\u044b\u043b. \u0412 \u0442\u0440\u0435\u0442\u044c\u0435\u043c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0440\u0430\u0437\u0431\u0438\u0442\u044c \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b \u0443\u0437\u043b\u0430 \u043d\u0430 \u043f\u043e\u0434\u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b \u0434\u043e \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0435\u0439 \u0442\u043e\u0447\u043a\u0438 \u0437\u0430\u0434\u0430\u0432\u0430\u0435\u043c\u043e\u0433\u043e \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u0430, \u0438 \u043d\u0430 \u0442\u043e, \u0447\u0442\u043e \u043e\u0441\u0442\u0430\u043b\u043e\u0441\u044c. \u041f\u043e\u0442\u043e\u043c \u0443\u0434\u0430\u043b\u0438\u0442\u044c \u0432\u0441\u0435 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u044b \u043f\u0435\u0440\u0435\u043a\u0440\u044b\u043b\u0438.<\/p>\n<p><a href=\"http:\/\/java.mazurok.com\/wp-content\/uploads\/Untitled.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-503\" src=\"http:\/\/java.mazurok.com\/wp-content\/uploads\/Untitled-300x132.jpg\" alt=\"Untitled\" width=\"570\" height=\"251\" srcset=\"https:\/\/java.mazurok.com\/wp-content\/uploads\/Untitled-300x132.jpg 300w, https:\/\/java.mazurok.com\/wp-content\/uploads\/Untitled.jpg 545w\" sizes=\"(max-width: 570px) 100vw, 570px\" \/><\/a><\/p>\n<p>\u041c\u0435\u0442\u043e\u0434 \u043f\u043e\u0438\u0441\u043a\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u0430\u043a \u0438 \u0432 \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u043c \u0434\u0435\u0440\u0435\u0432\u0435, \u043f\u043e\u043a\u0430 \u043d\u0435 \u043f\u043e\u043f\u0430\u0434\u0435\u043c \u043d\u0430 \u043d\u0443\u0436\u043d\u044b\u0439 \u043d\u0430\u043c \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b, \u0438\u043b\u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0430 \u0435\u0449\u0435 \u043d\u0435 \u0431\u044b\u043b\u043e \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d\u043e.<\/p>\n<p>\u041c\u0435\u0442\u043e\u0434 \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u043c\u0438\u043d\u0438\u043c\u0443\u043c\u0430 \u043d\u0430 \u043f\u043e\u0434\u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u0430 \u0441\u043f\u0443\u0441\u043a\u0430\u0435\u0442\u0441\u044f \u043f\u043e \u0434\u0435\u0440\u0435\u0432\u0443, \u043f\u043e\u043a\u0430 \u043d\u0435 \u043f\u043e\u043f\u0430\u0434\u0435\u0442 \u043d\u0430 \u043d\u0443\u0436\u043d\u044b\u0439 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b, \u0438 \u043f\u043e\u0442\u043e\u043c \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0438\u0437 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u043e\u0432 \u0438 \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u0442 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439.<\/p>\n<p>\u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0443 \u043d\u0430\u0441 \u0434\u0435\u0440\u0435\u0432\u043e \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043e \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443, \u0442\u043e \u0438\u0441\u043a\u0430\u0442\u044c \u0438\u043d\u0434\u0435\u043a\u0441 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043f\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044e \u0441\u043b\u043e\u0436\u043d\u0435\u0435, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043f\u0440\u043e\u0439\u0442\u0438 \u0432\u0441\u0435 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u044b \u043e\u0442 \u0438\u043d\u0434\u0435\u043a\u0441\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0430\u043c \u0434\u0430\u043b\u0438 \u0432 \u043d\u0430\u0447\u0430\u043b\u0435, \u043f\u043e\u043a\u0430 \u043d\u0435 \u0432\u0441\u0442\u0440\u0435\u0442\u0438\u043c \u0438\u0441\u043a\u043e\u043c\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u0438\u043b\u0438 \u0436\u0435 \u0432\u044b\u0432\u0435\u0434\u0435\u043c, \u0447\u0442\u043e \u0435\u0433\u043e \u043d\u0435\u0442.<\/p>\n<p>\u0422\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u043e\u0446\u0435\u043d\u043a\u0430 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u043c\u0435\u0442\u043e\u0434\u043e\u0432:<\/p>\n<ul>\n<li>get(i): O(log(count(set)));<\/li>\n<li>set(x, y, val): O(log(count(set)));<\/li>\n<li>indexof(val, index): O(count(set() &#8212; interval(index)));<\/li>\n<li>min(x, y) :\u00a0O(count(set()))<\/li>\n<\/ul>\n<pre class=\"lang:java decode:true \">\u041f\u0435\u0440\u0432\u044b\u0439 Set \u0432 BigSegmentedArray \u043e\u0442\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u0442 \u0437\u0430 436345 \u043d\u0441.\r\nGet \u0432 BigSegmentedArray \u043e\u0442\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u0442 \u0437\u0430 7700 \u043d\u0441.\r\n14\r\n\u0412\u0442\u043e\u0440\u043e\u0439 Set \u0432 BigSegmentedArray \u043e\u0442\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u0442 \u0437\u0430 4991 \u043d\u0441.\r\nMin \u0432 BigSegmentedArray \u043e\u0442\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u0442 \u0437\u0430 17883 \u043d\u0441.\r\n1<\/pre>\n<p><a href=\"http:\/\/ideone.com\/KEog4C\">\u0421\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 ideone.<\/a><\/p>\n<p>&nbsp;<\/p>\n<pre class=\"\">\/**\r\n * Created by green on 28.11.15.\r\n *\/\r\n\r\nimport jdk.internal.org.objectweb.asm.tree.analysis.Value;\r\n\r\nimport java.security.Key;\r\n\r\n\/**\r\n * Created by green on 26.11.15.\r\n *\/\r\n\r\ninterface SegmentedArray&lt;T&gt; {\r\n    \/**\r\n     * &lt;p&gt;Get value by element index&lt;\/p&gt;\r\n     * @param index index of element.\r\n     * @return  Value of element with specified index.\r\n     *\/\r\n    T get(int index);\r\n\r\n    \/**\r\n     * &lt;p&gt;Set the same value for all elements in the specified index range&lt;\/p&gt;\r\n     * @param start the beginning index, inclusive.\r\n     * @param end the ending index, exclusive.\r\n     * @param value value for.\r\n     *\/\r\n    void set(int start, int end, T value);\r\n\r\n    \/**\r\n     * &lt;p&gt;Returns the index within this array of the first occurrence of the specified value,\r\n     * starting at the specified index. If no such value of k exists, then -1 is returned.&lt;\/p&gt;\r\n     * @param value the T-based value for which to search.\r\n     * @param fromIndex the index from which to start the search.\r\n     * @return the index within this array of the first occurrence of the element with specified value,\r\n     * starting at the specified index.\r\n     *\/\r\n     int indexOf(T value, int fromIndex);\r\n\r\n    \/**\r\n     * &lt;p&gt;Find minimum value in the specified indexes range&lt;\/p&gt;\r\n     * @param start the beginning index, inclusive.\r\n     * @param end the ending index, exclusive.\r\n     * @return Minimum value.\r\n     *\/\r\n     T minValue(int start, int end);\r\n}\r\n\r\n\r\nclass CT &lt;Value extends Comparable&lt;Value&gt;&gt;  implements SegmentedArray&lt;Value&gt;{\r\n\r\n    private class Node {\r\n        Value value;\r\n        int l, r;\r\n        Node left, right, father;\r\n        public Node (Value value, Node father, int l, int r) {\r\n            this.value = value;\r\n            this.left = this.right = null;\r\n            this.father = father;\r\n            this.l = l; this.r = r;\r\n        }\r\n    }\r\n\r\n    private Node root;\r\n\r\n    private Node add (Node node,Value value, Node father, int l, int r){\r\n        if (node == null){\r\n            Node newnode = new Node(value,father, l , r);\r\n            return newnode;\r\n        }\r\n        \/\/int compareResultl = l.compareTo(node.l);\r\n        \/\/int compareResultr = r.compareTo(node.r);\r\n        if(l &gt; node.r){\r\n            node.right = add(node.right, value, node, l, r);\r\n        }else if(r &lt; node.l){\r\n            node.left = add(node.left, value, node, l, r);\r\n        }else if(l &gt;= node.l &amp;&amp; r &lt;= node.r){\r\n            if(l == node.l &amp;&amp; r == node.r){\r\n                node.value = value;\r\n                return node;\r\n            }else if(l == node.l){\r\n                node.right = add(node.right, node.value, node, r+1, node.r);\r\n                node.value = value;\r\n                node.r = r;\r\n            }else if(r == node.r){\r\n                node.left = add(node.left, node.value, node, node.l, l-1);\r\n                node.value = value;\r\n                node.l = l;\r\n            }else{\r\n                Node newnode = new Node(value,father, l , r);\r\n                newnode.left = node.left;\r\n                newnode.right = node.right;\r\n                newnode.left = add(newnode.left, node.value, newnode, node.l, l-1);\r\n                newnode.right = add(newnode.right, node.value, newnode, r+1, node.r);\r\n                node = newnode;\r\n            }\r\n        }else if(l &lt; node.l &amp;&amp; r &gt; node.r){\r\n            node.value = value;\r\n            node.l = l;\r\n            node.r = r;\r\n            node.left = delete(node.left, l, false);\r\n            node.right = delete(node.right, r, true);\r\n        }else if(l &lt; node.l){\r\n            if(r == node.r){\r\n                node.value = value;\r\n                node.l = l;\r\n                node.left = delete(node.left, l, false);\r\n            }else{\r\n                node = add(node, node.value, father, r+1, node.r);\r\n                node = add(node, value, father, l, r);\r\n            }\r\n        }else if (r &gt; node.r) {\r\n            if (l == node.l) {\r\n                node.value = value;\r\n                node.r = r;\r\n                node.right = delete(node.right, r, true);\r\n            } else {\r\n                node = add(node, node.value, father, node.l, l - 1);\r\n                node = add(node, value, father, l, r);\r\n            }\r\n        }\r\n        return node;\r\n    }\r\n\r\n    public void set(int l, int r, Value value) {\r\n        root = add(root, value, null, l, r);\r\n    }\r\n    private Node delete(Node node, int d, Boolean side){\r\n        if(node == null) return null;\r\n        if(d &lt; node.r &amp;&amp; d &gt; node.l){\r\n            node = add(node, node.value, node.father, node.l, d - 1);\r\n            node = delete(node, d, side);\r\n        }else if(d &lt; node.l){\r\n            if(side)\r\n                node.left = delete(node.left, d, side);\r\n            else {\r\n                node = node.left;\r\n                node = delete(node, d, side);\r\n            }\r\n        }else if(d &gt; node.r){\r\n            if(side) {\r\n                node = node.right;\r\n                node = delete(node, d, side);\r\n            }else\r\n                node.right = delete(node.right, d, side);\r\n        }else if(d == node.r){\r\n            if(side) {node = node.right;} else {node.right = null;node.r = d - 1;}\r\n        }else if(d == node.l){\r\n            if(side) {node.left = null;node.l = d + 1;} else {node = node.left;}\r\n        }\r\n        return node;\r\n    }\r\n\r\n    private Value get(Node node, int index){\r\n        if(node == null) return null;\r\n        if(index &gt; node.r)\r\n            return get(node.right, index);\r\n        else if (index &lt; node.l)\r\n            return get(node.left, index);\r\n        else\r\n            return node.value;\r\n    }\r\n\r\n    public Value get(int index) {\r\n        return get(root, index);\r\n    }\r\n\r\n    private Value minimum(Value x, Value y){\r\n        if(x == null &amp;&amp; y == null) return null;\r\n        else if(x == null) return y;\r\n        else if(y == null) return x;\r\n        else {\r\n            if (x.compareTo(y) == 1) return y;\r\n            else return x;\r\n        }\r\n    }\r\n\r\n    private Value min(Node node, int start, int end){\r\n        if(node == null) return null;\r\n        if(end &lt; node.l){\r\n            return min(node.left, start, end);\r\n        }else if (start &gt; node.r){\r\n            return min(node.right, start, end);\r\n        }else{\r\n            Value v1 = null, v2 = null;\r\n            if(start &lt; node.l) v1 = min(node.left, start, end);\r\n            if(end &gt; node.r) v2 = min(node.right, start, end);\r\n            return minimum(v2, minimum(node.value, v1));\r\n        }\r\n    }\r\n\r\n    public Value minValue(int start, int end){\r\n        return min(root, start, end);\r\n    }\r\n\r\n    private Integer indexOf(Node node, Value value, int index){\r\n        if(node == null) return null;\r\n        if(index &lt;= node.r) {\r\n            Integer v = null;\r\n            if(index &lt; node.l){\r\n                v = indexOf(node.left, value, index);\r\n                if (v != null) return v;\r\n            }\r\n            if (value == node.value) return Math.max(node.l, index);\r\n            v = indexOf(node.right, value, index);\r\n            if (v != null) return v;\r\n        }\r\n        return indexOf(node.right, value, index);\r\n    }\r\n\r\n    public int indexOf(Value value, int index){\r\n        return indexOf(root, value, index);\r\n    }\r\n\r\n    private void print(Node node, int level) {\r\n        if (node != null) {\r\n            print(node.right,level+1);\r\n            for (int i=0;i&lt;level;i++) {\r\n                System.out.print(\"\\t\");\r\n            }\r\n            System.out.println(node.l + \"-\" + node.r + \"-&gt;\" + node.value);\r\n            print(node.left,level+1);\r\n        }\r\n    }\r\n\r\n    public void print() {\r\n        print(root,0);\r\n    }\r\n\r\n}\r\n\r\n\r\npublic class Tree_cut {\r\n    public static void main(String[] args) {\r\n        CT&lt;Integer&gt; tree = new CT&lt;&gt;();\r\n        long start, end;\r\n        start = System.nanoTime();\r\n        tree.set(50, 4566, 14);\r\n        \/\/tree.set(130, 740, 29012);\r\n        \/\/tree.set(1000, 1084, -2);\r\n        \/\/tree.set(3006, 3070, 51);\r\n        end = System.nanoTime();\/\/tree.set(50, 4566, 14);\r\n        System.out.println(\"\u041f\u0435\u0440\u0432\u044b\u0439 Set \u0432 BigSegmentedArray \u043e\u0442\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u0442 \u0437\u0430 \" + (end - start) + \" \u043d\u0441.\");\r\n\r\n        start = System.nanoTime();\r\n        Integer get = tree.get(111);\r\n        end = System.nanoTime();\r\n        System.out.println(\"Get \u0432 BigSegmentedArray \u043e\u0442\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u0442 \u0437\u0430 \" + (end - start) + \" \u043d\u0441.\");\r\n        System.out.println(get);\r\n\r\n        start = System.nanoTime();\r\n        tree.set(76, 830, 1);\r\n        end = System.nanoTime();\r\n        System.out.println(\"\u0412\u0442\u043e\u0440\u043e\u0439 Set \u0432 BigSegmentedArray \u043e\u0442\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u0442 \u0437\u0430 \" + (end - start) + \" \u043d\u0441.\");\r\n        tree.set(60, 92, 0);\r\n\r\n        start = System.nanoTime();\r\n        int minimum = tree.minValue(130, 1400);\r\n        end = System.nanoTime();\r\n        System.out.println(\"Min \u0432 BigSegmentedArray \u043e\u0442\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u0442 \u0437\u0430 \" + (end - start) + \" \u043d\u0441.\");\r\n        System.out.println(minimum);\r\n        tree.print();\r\n    }\r\n}<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u041c\u043d\u0435 \u043f\u0440\u0435\u0434\u043e\u0441\u0442\u0430\u0432\u0438\u043b\u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043a\u043b\u0430\u0441\u0441, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0430\u0441\u043b\u0435\u0434\u0443\u0435\u0442 SegmentedArray \u0438 \u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u0438\u0437\u0443\u0435\u0442\u0441\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c: \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \u0447\u0430\u0441\u0442\u044b\u0435 \u0437\u0430\u043f\u0440\u043e\u0441\u044b get(), min(); \u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043a\u043e\u043c\u0430\u043d\u0434\u0430 set\u00a0\u0437\u0430\u0434\u0430\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043d\u0430 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u0435, \u044f \u0440\u0435\u0448\u0438\u043b \u0441\u0434\u0435\u043b\u0430\u0442\u044c &#171;\u0434\u0435\u0440\u0435\u0432\u043e \u043e\u0442\u0440\u0435\u0437\u043a\u043e\u0432&#187;. \u041a\u043e\u0442\u043e\u0440\u043e\u0435 \u0443\u0441\u0442\u0440\u043e\u0435\u043d\u043e \u043a\u0430\u043a \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0430 (\u0432 \u0437\u0430\u0434\u0430\u043d\u0438\u0438 \u0431\u043e\u043b\u044c\u0448\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0437\u0430\u043f\u0440\u043e\u0441\u043e\u0432 get(), \u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0438\u0441\u043a\u0430\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443), \u0438\u043c\u0435\u044f \u0432 \u0441\u0435\u0431\u0435 \u043b\u0435\u0432\u044b\u0439 \u0438 \u043f\u0440\u0430\u0432\u044b\u0435 \u043a\u043e\u043d\u0446\u044b &hellip; <a href=\"https:\/\/java.mazurok.com\/?p=411\" class=\"more-link\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":33,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[49],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts\/411"}],"collection":[{"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/users\/33"}],"replies":[{"embeddable":true,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=411"}],"version-history":[{"count":8,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts\/411\/revisions"}],"predecessor-version":[{"id":579,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts\/411\/revisions\/579"}],"wp:attachment":[{"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=411"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=411"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=411"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}