{"id":297503,"date":"2020-01-22T15:00:21","date_gmt":"2020-01-22T15:00:21","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=297503"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=297503","title":{"rendered":"\u041a\u043e\u0442\u044b \u0432 \u043a\u043e\u0440\u043e\u0431\u043e\u0447\u043a\u0430\u0445, \u0438\u043b\u0438 \u041a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u044b\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445"},"content":{"rendered":"\n<div class=\"post__text post__text-html\" id=\"post-content-body\" data-io-article-url=\"https:\/\/habr.com\/ru\/company\/mailru\/blog\/479822\/\">\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/uv\/si\/qc\/uvsiqcnik2vqvi6zzwvjifbrv2w.jpeg\" alt=\"image\"><\/p>\n<p>  <\/p>\n<p>\u041a\u0430\u043a \u0431\u044b\u0442\u044c, \u0435\u0441\u043b\u0438 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0438\u0441\u043a\u0430 \u0440\u0430\u0437\u0440\u043e\u0441\u043b\u043e\u0441\u044c \u043d\u0430 \u0432\u0441\u044e \u043e\u043f\u0435\u0440\u0430\u0442\u0438\u0432\u043a\u0443 \u0438 \u0432\u043e\u0442-\u0432\u043e\u0442 \u043f\u043e\u0434\u043e\u043f\u0440\u0435\u0442 \u043a\u043e\u0440\u043d\u044f\u043c\u0438 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0435 \u0441\u0442\u043e\u0439\u043a\u0438 \u0432 \u0441\u0435\u0440\u0432\u0435\u0440\u043d\u043e\u0439? \u0427\u0442\u043e \u0434\u0435\u043b\u0430\u0442\u044c \u0441 \u0438\u043d\u0432\u0435\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u043c \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u043c, \u0436\u0430\u0434\u043d\u044b\u043c \u0434\u043e \u0440\u0435\u0441\u0443\u0440\u0441\u043e\u0432?\u00a0\u0417\u0430\u0432\u044f\u0437\u044b\u0432\u0430\u0442\u044c \u043b\u0438 \u0441 \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u043a\u043e\u0439 \u043f\u043e\u0434 Android, \u0435\u0441\u043b\u0438 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044e \u043f\u0440\u0438\u043b\u0435\u0442\u0430\u0435\u0442 \u00ab\u041f\u0430\u043c\u044f\u0442\u044c \u0442\u0435\u043b\u0435\u0444\u043e\u043d\u0430 \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u0430\u00bb, \u0430 \u043f\u0440\u0438\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u0435\u0434\u0432\u0430 \u043d\u0430 \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0435 \u0437\u0430\u0433\u0440\u0443\u0437\u043a\u0438 \u0432\u0430\u0436\u043d\u043e\u0433\u043e \u043a\u043e\u043d\u0442\u0435\u0439\u043d\u0435\u0440\u0430?<\/p>\n<p>  <\/p>\n<p>\u0412 \u0446\u0435\u043b\u043e\u043c, \u043c\u043e\u0436\u043d\u043e \u043b\u0438 \u0441\u0436\u0430\u0442\u044c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0434\u0430\u043d\u043d\u044b\u0445, \u0447\u0442\u043e\u0431\u044b \u043e\u043d\u0430 \u0437\u0430\u043d\u0438\u043c\u0430\u043b\u0430 \u0437\u0430\u043c\u0435\u0442\u043d\u043e \u043c\u0435\u043d\u044c\u0448\u0435 \u043c\u0435\u0441\u0442\u0430, \u043d\u043e \u043d\u0435 \u0442\u0435\u0440\u044f\u043b\u0430 \u043f\u0440\u0438\u0441\u0443\u0449\u0438\u0445 \u0435\u0439 \u0434\u043e\u0441\u0442\u043e\u0438\u043d\u0441\u0442\u0432? \u0427\u0442\u043e\u0431\u044b \u0434\u043e\u0441\u0442\u0443\u043f \u043a \u0445\u044d\u0448-\u0442\u0430\u0431\u043b\u0438\u0446\u0435 \u043e\u0441\u0442\u0430\u0432\u0430\u043b\u0441\u044f \u0431\u044b\u0441\u0442\u0440\u044b\u043c, \u0430 \u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u043b\u043e \u0441\u0432\u043e\u0438 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430. \u0414\u0430, \u043c\u043e\u0436\u043d\u043e! \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0438 \u043f\u043e\u044f\u0432\u0438\u043b\u043e\u0441\u044c \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0442\u0438\u043a\u0438 \u00abSuccinct data structures\u00bb, \u0438\u0441\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435 \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u043e\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u0434\u0430\u043d\u043d\u044b\u0445. \u041e\u043d\u043e \u0440\u0430\u0437\u0432\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0441 \u043a\u043e\u043d\u0446\u0430 80-\u0445 \u0433\u043e\u0434\u043e\u0432 \u0438 \u043f\u0440\u044f\u043c\u043e \u0441\u0435\u0439\u0447\u0430\u0441 \u043f\u0435\u0440\u0435\u0436\u0438\u0432\u0430\u0435\u0442 \u0440\u0430\u0441\u0446\u0432\u0435\u0442 \u0432 \u043b\u0443\u0447\u0430\u0445 \u0441\u043b\u0430\u0432\u044b big data \u0438 highload.<\/p>\n<p>  <\/p>\n<p>\u0410 \u0442\u0435\u043c \u0432\u0440\u0435\u043c\u0435\u043d\u0435\u043c \u043d\u0430 \u0425\u0430\u0431\u0440\u0435 \u043d\u0430\u0439\u0434\u0435\u0442\u0441\u044f \u043b\u0438 \u0433\u0435\u0440\u043e\u0439, \u0441\u043f\u043e\u0441\u043e\u0431\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0441\u043a\u043e\u0432\u043e\u0433\u043e\u0432\u043e\u0440\u0438\u0442\u044c \u0442\u0440\u0438 \u0440\u0430\u0437\u0430 \u043f\u043e\u0434\u0440\u044f\u0434<br \/>  [s\u0259k\u02c8s\u026a\u014bkt]?<\/p>\n<p><a name=\"habracut\"><\/a>  <\/p>\n<h2 id=\"dver-v-mir-kompaktnosti\">\u0414\u0432\u0435\u0440\u044c \u0432 \u043c\u0438\u0440 \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u043e\u0441\u0442\u0438<\/h2>\n<p>  <\/p>\n<p>\u0418\u0442\u0430\u043a, \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u0441\u0447\u0438\u0442\u0430\u0435\u0442\u0441\u044f \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u043e\u0439 (succinct), \u0435\u0441\u043b\u0438 \u043e\u043d\u0430:<\/p>\n<p>  <\/p>\n<ul>\n<li>\u0417\u0430\u043d\u0438\u043c\u0430\u0435\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0438\u0442, \u0431\u043b\u0438\u0437\u043a\u043e\u0435 \u043a \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u043e\u043d\u043d\u043e-\u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043d\u0438\u0436\u043d\u0435\u0439 \u0433\u0440\u0430\u043d\u0438\u0446\u0435.<\/li>\n<li>\u041d\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u043f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0440\u0430\u0441\u043f\u0430\u043a\u043e\u0432\u043a\u0438 \u0434\u043b\u044f \u043f\u043e\u043b\u043d\u043e\u0446\u0435\u043d\u043d\u043e\u0433\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f.<\/li>\n<\/ul>\n<p>  <\/p>\n<p>\u042d\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0441\u0436\u0430\u0442\u0438\u044f \u0431\u0435\u0437 \u043f\u043e\u0442\u0435\u0440\u044c \u043d\u0438\u043a\u0430\u043a\u043e\u0433\u043e \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u044f \u043a \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u044b\u043c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430\u043c \u0434\u0430\u043d\u043d\u044b\u0445 \u043d\u0435 \u0438\u043c\u0435\u044e\u0442. \u0412\u0435\u0434\u044c \u043e\u043d\u0438 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u044e\u0442 \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u0435 \u0434\u0430\u043d\u043d\u044b\u0445 \u0438\u0437 \u0441\u0436\u0430\u0442\u043e\u0433\u043e \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0434\u043b\u044f \u0438\u0445 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0438. <\/p>\n<p>  <\/p>\n<p>\u041f\u0440\u0438\u0432\u044b\u0447\u043d\u044b\u0435, \u00ab\u043c\u0435\u0439\u043d\u0441\u0442\u0440\u0438\u043c\u043e\u0432\u044b\u0435\u00bb \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0433\u0440\u0430\u0444\u043e\u0432, \u0445\u044d\u0448-\u0442\u0430\u0431\u043b\u0438\u0446 \u0438 \u043f\u0440\u043e\u0447\u0435\u0433\u043e \u0442\u043e\u0436\u0435 \u043d\u0435 \u0433\u043e\u0434\u044f\u0442\u0441\u044f. \u0412\u0437\u044f\u0442\u044c \u0445\u043e\u0442\u044f \u0431\u044b \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0438 \u043d\u0430 \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0432 \u0434\u0435\u0440\u0435\u0432\u0435 \u043f\u043e\u0438\u0441\u043a\u0430.\u00a0\u041e\u043d\u0438 \u043e\u0442\u044a\u0435\u0434\u0430\u044e\u0442 \u043f\u043e\u0440\u044f\u0434\u043e\u0447\u043d\u043e \u043c\u0435\u0441\u0442\u0430: <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/135\/ab2\/4a1\/135ab24a11ffb0e9a57e87a7443c0455.svg\" alt=\"$O(MN)$\" data-tex=\"inline\"><\/math>, \u0433\u0434\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/94d\/13e\/e0a\/94d13ee0aadd7f17977e0d279af38d42.svg\" alt=\"$M$\" data-tex=\"inline\"><\/math> \u2014 \u0434\u043b\u0438\u043d\u0430 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f, \u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1e8\/0c3\/b30\/1e80c3b3087c0a57b68ad11261a9ec2b.svg\" alt=\"$N$\" data-tex=\"inline\"><\/math> \u2014\u00a0\u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0443\u0437\u043b\u043e\u0432 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435. \u0417\u0430\u0442\u043e succinct \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0434\u0435\u0440\u0435\u0432\u0430 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0443\u043b\u0443\u0447\u0448\u0438\u0442\u044c \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u043a\u0443 \u0434\u043e\u00a0<math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/788\/906\/c12\/788906c124edd90129fbd06f990d3a43.svg\" alt=\"$2N + o(N)$\" data-tex=\"inline\"><\/math>, \u0447\u0442\u043e \u0431\u043b\u0438\u0437\u043a\u043e \u043a \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043d\u0438\u0436\u043d\u0435\u0439 \u0433\u0440\u0430\u043d\u0438\u0446\u0435\u00a0<math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/272\/e51\/dd7\/272e51dd7d4c889b8747deb77ef6c676.svg\" alt=\"$2N \u2212 \u0398(log N)$\" data-tex=\"inline\"><\/math> \u0434\u043b\u044f \u0434\u0435\u0440\u0435\u0432\u0430 \u0438\u0437 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1e8\/0c3\/b30\/1e80c3b3087c0a57b68ad11261a9ec2b.svg\" alt=\"$N$\" data-tex=\"inline\"><\/math> \u0443\u0437\u043b\u043e\u0432. \u041f\u0440\u0438 \u0434\u043b\u0438\u043d\u0435 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/54c\/0d8\/335\/54c0d8335820f020f41f22ababf2e47e.svg\" alt=\"$M=8$\" data-tex=\"inline\"><\/math> \u0431\u0430\u0439\u0442 \u044d\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442 \u043f\u0435\u0440\u0435\u0445\u043e\u0434 \u043e\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/485\/6d7\/bd2\/4856d7bd2a582bf7a29d30aece7843a0.svg\" alt=\"$O(8N)$\" data-tex=\"inline\"><\/math> \u043a \u0441\u043e\u0432\u0435\u0440\u0448\u0435\u043d\u043d\u043e \u0434\u0440\u0443\u0433\u043e\u043c\u0443 \u043f\u043e\u0440\u044f\u0434\u043a\u0443 \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u043a\u0438 \u2014 \u0432\u0441\u0435\u0433\u043e \u043b\u0438\u0448\u044c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/91f\/0c8\/61c\/91f0c861cea62f4cfcd5e395591a1c46.svg\" alt=\"$2N$\" data-tex=\"inline\"><\/math>, \u0435\u0441\u043b\u0438 \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u0442\u044c, \u0447\u0442\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b24\/fd3\/cb1\/b24fd3cb1341dee79adad126930a0373.svg\" alt=\"$o(N)$\" data-tex=\"inline\"><\/math> \u2014 \u043f\u0440\u0435\u043d\u0435\u0431\u0440\u0435\u0436\u0438\u043c\u043e \u043c\u0430\u043b\u0430\u044f \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u0430 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1e8\/0c3\/b30\/1e80c3b3087c0a57b68ad11261a9ec2b.svg\" alt=\"$N$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  <\/p>\n<p><strong>\u041a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u044b\u0435 (succinct) \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445<\/strong> \u2014 \u044d\u0442\u043e \u0441\u0436\u0430\u0442\u044b\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0434\u043b\u044f \u0431\u0438\u0442\u043e\u0432\u044b\u0445 \u0432\u0435\u043a\u0442\u043e\u0440\u043e\u0432, \u043c\u0443\u043b\u044c\u0442\u0438\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432, \u043f\u043b\u0430\u043d\u0430\u0440\u043d\u044b\u0445 \u0433\u0440\u0430\u0444\u043e\u0432 \u0438 \u0434\u0440\u0443\u0433\u0438\u0445 \u0432\u0441\u0435\u043c\u0438 \u043b\u044e\u0431\u0438\u043c\u044b\u0445 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440. \u0417\u0430\u0447\u0430\u0441\u0442\u0443\u044e \u043e\u043d\u0438 \u0441\u0442\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0435, \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u043d\u044b\u0435 \u0435\u0434\u0438\u043d\u043e\u0436\u0434\u044b \u0438 \u043d\u0435 \u043c\u0435\u043d\u044f\u044e\u0449\u0438\u0435\u0441\u044f \u0432 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f. \u0415\u0441\u0442\u044c \u0438 \u0438\u0441\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u044f \u2014 succinct-\u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0441 \u0431\u044b\u0441\u0442\u0440\u044b\u043c\u0438 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f\u043c\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432.<\/p>\n<p>  <\/p>\n<p>\u0412 \u043e\u0441\u043d\u043e\u0432\u0435 \u0431\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u0430 \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u044b\u0445 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u043b\u0435\u0436\u0438\u0442 \u043a\u043e\u043d\u0446\u0435\u043f\u0446\u0438\u044f \u0442\u0430\u043a \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u043e\u0433\u043e \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u043e\u0433\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0438\u0440\u0443\u0435\u043c\u043e\u0433\u043e \u0441\u043b\u043e\u0432\u0430\u0440\u044f. \u042d\u0442\u043e \u2014 \u0447\u0430\u0441\u0442\u043d\u044b\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 \u0431\u0438\u0442\u043e\u0432\u043e\u0439 \u043a\u0430\u0440\u0442\u044b (bitmap, bitset). \u0421\u0430\u043c\u0430 \u043f\u043e \u0441\u0435\u0431\u0435 \u0431\u0438\u0442\u043e\u0432\u0430\u044f \u043a\u0430\u0440\u0442\u0430 \u0438\u0434\u0435\u0430\u043b\u044c\u043d\u0430 \u0434\u043b\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u0432\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u043d\u0435\u043a\u043e\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e. \u0415\u0441\u043b\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0432\u043a\u043b\u044e\u0447\u0435\u043d \u0432 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e, \u0442\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0431\u0438\u0442\u0430 \u043f\u043e \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u043c\u0443 \u0438\u043d\u0434\u0435\u043a\u0441\u0443 \u0443\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0432 1, \u0435\u0441\u043b\u0438 \u043d\u0435\u0442 \u2014 \u0441\u0431\u0440\u0430\u0441\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0432 0. \u0416\u0438\u0437\u043d\u0435\u043d\u043d\u044b\u0439 \u043f\u0440\u0438\u043c\u0435\u0440 \u2014 inode-\u0431\u0438\u0442\u043c\u0430\u043f\u0430 ext4, UFS \u0438 \u0434\u0440\u0443\u0433\u0438\u0445 \u044e\u043d\u0438\u043a\u0441\u043e\u0432\u044b\u0445 \u0444\u0430\u0439\u043b\u043e\u0432\u044b\u0445 \u0441\u0438\u0441\u0442\u0435\u043c. \u041e\u043d\u0430 \u0445\u0440\u0430\u043d\u0438\u0442 \u0434\u0430\u043d\u043d\u044b\u0435 \u043e \u0442\u043e\u043c, \u043a\u0430\u043a\u0438\u0435 \u0437\u0430\u043f\u0438\u0441\u0438 \u0432 \u0442\u0430\u0431\u043b\u0438\u0446\u0435 \u0438\u043d\u0434\u0435\u043a\u0441\u043d\u044b\u0445 \u0434\u0435\u0441\u043a\u0440\u0438\u043f\u0442\u043e\u0440\u043e\u0432 \u0437\u0430\u043d\u044f\u0442\u044b, \u0430 \u043a\u0430\u043a\u0438\u0435 \u2014 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u044b.<\/p>\n<p>  <\/p>\n<p><b>\u041a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u044b\u0439 \u0438\u043d\u0434\u0435\u043a\u0441\u0438\u0440\u0443\u0435\u043c\u044b\u0439\u00a0\u0441\u043b\u043e\u0432\u0430\u0440\u044c<\/b> \u2014 \u044d\u0442\u043e \u0442\u0430 \u0436\u0435 \u0431\u0438\u0442\u043e\u0432\u0430\u044f \u043a\u0430\u0440\u0442\u0430, \u043d\u043e \u0434\u043e\u043f\u043e\u043b\u043d\u0435\u043d\u043d\u0430\u044f \u0434\u0432\u0443\u043c\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f\u043c\u0438: rank \u0438 select. \u042d\u0442\u0438 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u2014 \u0441\u043b\u043e\u043d\u044b, \u043d\u0430 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0437\u0438\u0436\u0434\u0435\u0442\u0441\u044f \u043c\u0438\u0440 succinct. \u0413\u0440\u0443\u0431\u043e \u0433\u043e\u0432\u043e\u0440\u044f, rank \u2014 \u044d\u0442\u043e \u043f\u043e\u0434\u0441\u0447\u0435\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u0430 select \u2014 \u043f\u043e\u0438\u0441\u043a \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430:<\/p>\n<p>  <\/p>\n<ul>\n<li><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/538\/132\/c73\/538132c73283aaa3e37ea9002b924233.svg\" alt=\"$rank_x(i)$\" data-tex=\"inline\"><\/math> \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0438\u0442, \u0440\u0430\u0432\u043d\u044b\u0445 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/817\/b92\/407\/817b92407f764f57af9226e50cc788fd.svg\" alt=\"$x$\" data-tex=\"inline\"><\/math>, \u0447\u044c\u0438 \u0438\u043d\u0434\u0435\u043a\u0441\u044b \u043b\u0435\u0436\u0430\u0442 \u043d\u0430 \u043e\u0442\u0440\u0435\u0437\u043a\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bdc\/2df\/012\/bdc2df01273ee674ef795840b2c1a059.svg\" alt=\"$[0; i]$\" data-tex=\"inline\"><\/math>. \u0422\u0430\u043a \u043a\u0430\u043a <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/817\/b92\/407\/817b92407f764f57af9226e50cc788fd.svg\" alt=\"$x$\" data-tex=\"inline\"><\/math> \u2014 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0431\u0438\u0442\u0430, \u0442\u043e \u043e\u043d \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0440\u0430\u0432\u0435\u043d \u0438\u0441\u043a\u043b\u044e\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e 0 \u0438\u043b\u0438 1.<\/li>\n<li><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d90\/e1b\/369\/d90e1b36935170287adbc8d05ef1c998.svg\" alt=\"$select_x(j)$\" data-tex=\"inline\"><\/math> \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0438\u043d\u0434\u0435\u043a\u0441 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b82\/8e2\/475\/b828e2475a3a56280b895f35eb250ea2.svg\" alt=\"$j$\" data-tex=\"inline\"><\/math>-\u0433\u043e \u0431\u0438\u0442\u0430, \u0440\u0430\u0432\u043d\u043e\u0433\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/817\/b92\/407\/817b92407f764f57af9226e50cc788fd.svg\" alt=\"$x$\" data-tex=\"inline\"><\/math>. \u0417\u0434\u0440\u0430\u0432\u044b\u0439 \u0441\u043c\u044b\u0441\u043b \u0433\u043e\u0432\u043e\u0440\u0438\u0442, \u0447\u0442\u043e \u043d\u0443\u043b\u0435\u0432\u043e\u0433\u043e \u0432\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u043d\u0435 \u0431\u044b\u0432\u0430\u0435\u0442, \u0435\u0441\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0435\u0440\u0432\u043e\u0435. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 <math>$inline$j &gt; 0$inline$<\/math>: \u043f\u043e\u0434\u0441\u0447\u0435\u0442 \u0432\u0435\u0434\u0435\u0442\u0441\u044f \u043e\u0442 \u0435\u0434\u0438\u043d\u0438\u0446\u044b. \u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b82\/8e2\/475\/b828e2475a3a56280b895f35eb250ea2.svg\" alt=\"$j$\" data-tex=\"inline\"><\/math> \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u0442\u044c \u0441\u0443\u043c\u043c\u0430\u0440\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0438\u0442\u043e\u0432 \u0432 \u0441\u043b\u043e\u0432\u0430\u0440\u0435, \u0440\u0430\u0432\u043d\u044b\u0445 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/817\/b92\/407\/817b92407f764f57af9226e50cc788fd.svg\" alt=\"$x$\" data-tex=\"inline\"><\/math>.<\/li>\n<\/ul>\n<p>  <\/p>\n<p>\u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c, \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u0438\u043d\u0434\u0435\u043a\u0441\u0438\u0440\u0443\u0435\u043c\u044b\u0439 \u0441\u043b\u043e\u0432\u0430\u0440\u044c, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c 4 \u0438\u0437 7 \u0431\u0438\u0442 \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d\u044b. \u0422\u043e\u0433\u0434\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/130\/92b\/70a\/13092b70a9bcd9f531a7b48824ede4ce.svg\" alt=\"$rank_1$\" data-tex=\"inline\"><\/math> \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/316\/750\/252\/3167502521b2ee313ff242f481af63d6.svg\" alt=\"$select_1$\" data-tex=\"inline\"><\/math> \u043f\u0440\u0438\u043c\u0443\u0442 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f:<\/p>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/1v\/ly\/i1\/1vlyi1c_rbaafr2igbws11bgini.jpeg\" width=\"400\"><\/div>\n<p>  <\/p>\n<p><em>\u041f\u0440\u0438\u043c\u0435\u0440 \u0438\u043d\u0434\u0435\u043a\u0441\u0438\u0440\u0443\u0435\u043c\u043e\u0433\u043e \u0441\u043b\u043e\u0432\u0430\u0440\u044f \u0438 \u0440\u0430\u0441\u0447\u0435\u0442\u0430 \u0434\u043b\u044f \u043d\u0435\u0433\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/130\/92b\/70a\/13092b70a9bcd9f531a7b48824ede4ce.svg\" alt=\"$rank_1$\" data-tex=\"inline\"><\/math>, <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/316\/750\/252\/3167502521b2ee313ff242f481af63d6.svg\" alt=\"$select_1$\" data-tex=\"inline\"><\/math>.<\/em><\/p>\n<p>  <\/p>\n<p>\u0412\u043d\u0438\u043c\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u044c \u0437\u0430\u043c\u0435\u0442\u0438\u0442, \u0447\u0442\u043e select \u2014 \u043e\u0431\u0440\u0430\u0442\u043d\u0430\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u0434\u043b\u044f rank. \u0415\u0441\u043b\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9d1\/fa5\/275\/9d1fa52759127ccc2bfcfcaaca541ea6.svg\" alt=\"$rank_1(5) = 4$\" data-tex=\"inline\"><\/math>, \u0442\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/f54\/e2b\/928\/f54e2b92810e00f7bae581c8b69ffe3f.svg\" alt=\"$select_1(4)=5$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  <\/p>\n<p>\u0423 \u043a\u043e\u0433\u043e-\u043d\u0438\u0431\u0443\u0434\u044c \u0432\u043e\u0437\u043d\u0438\u043a\u043b\u043e \u0434\u0435\u0436\u0430\u0432\u044e \u043f\u0440\u0438 \u0432\u0438\u0434\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/cc7\/e67\/400\/cc7e674008743ea4eb37d8409ab0a75d.svg\" alt=\"$rank_1(i)$\" data-tex=\"inline\"><\/math>? \u0410 \u0432\u0441\u0435 \u043f\u043e\u0442\u043e\u043c\u0443, \u0447\u0442\u043e \u044d\u0442\u0430 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u043e\u0431\u043e\u0431\u0449\u0430\u0435\u0442 \u0412\u0435\u0441 \u0425\u044d\u043c\u043c\u0438\u043d\u0433\u0430 \u2014 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043d\u0435 \u043d\u0443\u043b\u0435\u0432\u044b\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0432 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438. \u041f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043a \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u043c \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044f\u043c \u0412\u0435\u0441 \u0425\u044d\u043c\u043c\u0438\u043d\u0433\u0430 \u0442\u0430\u043a\u0436\u0435 \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f <strong>popcount<\/strong> (population count).<\/p>\n<p>  <\/p>\n<p>Rank\/select \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c\u044b \u0438 \u0434\u043b\u044f \u0441\u0431\u0440\u043e\u0448\u0435\u043d\u043d\u044b\u0445 \u0431\u0438\u0442\u043e\u0432. \u0412\u043e\u0442 \u043f\u0440\u0438\u043c\u0435\u0440 \u0440\u0430\u0441\u0447\u0435\u0442\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/85b\/632\/b18\/85b632b18a80ada5891b8870f71989e0.svg\" alt=\"$rank_0$\" data-tex=\"inline\"><\/math> \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/f9a\/c21\/872\/f9ac218728f2c41e530465b549fef7ed.svg\" alt=\"$select_0$\" data-tex=\"inline\"><\/math> \u0434\u043b\u044f \u0431\u0438\u0442\u043e\u0432, \u0440\u0430\u0432\u043d\u044b\u0445 0:<\/p>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/0f\/ef\/nx\/0fefnxyz85hi0jjtwlg6nal357a.jpeg\" width=\"400\"><\/div>\n<p>  <\/p>\n<p><em>\u041f\u0440\u0438\u043c\u0435\u0440 \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u043e\u0433\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0438\u0440\u0443\u0435\u043c\u043e\u0433\u043e \u0441\u043b\u043e\u0432\u0430\u0440\u044f \u0438 \u0440\u0430\u0441\u0447\u0435\u0442\u0430 \u0434\u043b\u044f \u043d\u0435\u0433\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/85b\/632\/b18\/85b632b18a80ada5891b8870f71989e0.svg\" alt=\"$rank_0$\" data-tex=\"inline\"><\/math>, <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/f9a\/c21\/872\/f9ac218728f2c41e530465b549fef7ed.svg\" alt=\"$select_0$\" data-tex=\"inline\"><\/math>.<\/em><\/p>\n<p>  <\/p>\n<h2 id=\"raspilit-derevo-na-bitiki\">\u0420\u0430\u0441\u043f\u0438\u043b\u0438\u0442\u044c \u0434\u0435\u0440\u0435\u0432\u043e \u043d\u0430 \u0431\u0438\u0442\u0438\u043a\u0438<\/h2>\n<p>  <\/p>\n<p>\u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u0436\u0435 \u044d\u0442\u043e \u0437\u043d\u0430\u043d\u0438\u0435, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u043e\u0435 \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e! \u041f\u0440\u0435\u0444\u0438\u043a\u0441\u043d\u044b\u0435 \u0434\u0435\u0440\u0435\u0432\u044c\u044f \u0445\u043e\u0440\u043e\u0448\u0438 \u0434\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u0441\u0442\u0440\u043e\u043a \u043f\u043e \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u0443. \u0421 \u0438\u0445 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0437\u0430\u0447\u0430\u0441\u0442\u0443\u044e \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u0442\u0441\u044f \u0432\u044b\u043f\u0430\u0434\u0430\u044e\u0449\u0438\u0439 \u0441\u043f\u0438\u0441\u043e\u043a \u043f\u043e\u0438\u0441\u043a\u043e\u0432\u044b\u0445 \u043f\u043e\u0434\u0441\u043a\u0430\u0437\u043e\u043a (\u0441\u0430\u0434\u0436\u0435\u0441\u0442). \u041f\u043e\u0434\u0445\u043e\u0434 \u043a succinct&#8217;\u0438\u0437\u0430\u0446\u0438\u0438 \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u043f\u0440\u0435\u0434\u0435\u043b\u044c\u043d\u043e \u043e\u0431\u043e\u0431\u0449\u0435\u043d\u043d\u044b\u0439 \u0438 \u043f\u043e-\u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c\u0443 \u0434\u0435\u043c\u043e\u043d\u0441\u0442\u0440\u0438\u0440\u0443\u0435\u0442 \u0432\u0435\u0441\u044c \u0438\u0437\u044e\u043c \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u044b\u0445 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440. \u0412 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0432\u044b\u0432\u0435\u0434\u0435\u043d\u044b \u0447\u0430\u0441\u0442\u043d\u044b\u0435 \u0444\u043e\u0440\u043c\u0443\u043b\u044b, \u043c\u0435\u0448\u0430\u044e\u0449\u0438\u0435 \u0443\u0432\u0438\u0434\u0435\u0442\u044c \u043e\u0431\u0449\u0443\u044e \u043a\u0430\u0440\u0442\u0438\u043d\u0443. <\/p>\n<p>  <\/p>\n<p>\u041f\u043e\u043f\u0443\u043b\u044f\u0440\u043d\u0435\u0435 \u0432\u0441\u0435\u0433\u043e \u0442\u0440\u0438 \u043c\u0435\u0442\u043e\u0434\u0430 \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u043e\u0433\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432:<\/p>\n<p>  <\/p>\n<ul>\n<li>BP (balanced parentheses) \u2014 \u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u0441\u043a\u043e\u0431\u043e\u0447\u043d\u044b\u0435 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438.<\/li>\n<li>DFUDS (depth-first unary degree sequence) \u2014 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0435\u0434\u0438\u043d\u0438\u0447\u043d\u043e-\u0437\u0430\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432, \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u043f\u043e\u0438\u0441\u043a\u043e\u043c \u0432 \u0433\u043b\u0443\u0431\u0438\u043d\u0443.<\/li>\n<li>LOUDS (level-ordered unary degree sequences) \u2014 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0435\u0434\u0438\u043d\u0438\u0447\u043d\u043e-\u0437\u0430\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432,\u00a0\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u043f\u043e \u0443\u0440\u043e\u0432\u043d\u044f\u043c.<\/li>\n<\/ul>\n<p>  <\/p>\n<p>\u0427\u0442\u043e \u0437\u0430 \u043f\u043e\u0434\u043e\u0437\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0446\u0435\u043f\u043e\u0447\u043a\u0430 \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0430 \u00abunary degree\u00bb \u0432 \u00ab\u0435\u0434\u0438\u043d\u0438\u0447\u043d\u043e-\u0437\u0430\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u0443\u0437\u0435\u043b\u00bb?\u00a0\u0427\u0442\u043e \u0436. Unary degree \u0432 \u044d\u0442\u0438\u0445 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u044f\u0445 \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442 \u0441\u043f\u043e\u0441\u043e\u0431 \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0443\u0437\u043b\u043e\u0432 \u0434\u0435\u0440\u0435\u0432\u0430 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c\u044e \u0435\u0434\u0438\u043d\u0438\u0446 \u043f\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0443 \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0445 \u0443\u0437\u043b\u043e\u0432, \u043e\u0431\u044f\u0437\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0441 \u043d\u0443\u043b\u0435\u043c \u0432 \u043f\u0440\u0438\u0446\u0435\u043f\u0435.<\/p>\n<p>  <\/p>\n<p>\u042d\u0442\u0438 \u0442\u0440\u0438 \u043c\u0435\u0442\u043e\u0434\u0430 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u043e\u0431\u044a\u0435\u0434\u0438\u043d\u044f\u0435\u0442 \u043d\u0430\u043b\u0438\u0447\u0438\u0435 \u0431\u044b\u0441\u0442\u0440\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439: \u043d\u0430\u0439\u0442\u0438 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f; \u043d\u0430\u0439\u0442\u0438 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u0430; \u043d\u0430\u0439\u0442\u0438 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u0430; \u043d\u0430\u0439\u0442\u0438 \u043b\u0435\u0432\u044b\u0439 \u0438 \u043f\u0440\u0430\u0432\u044b\u0439 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0435 \u0443\u0437\u043b\u044b. \u041f\u0440\u0438\u043d\u0446\u0438\u043f\u0438\u0430\u043b\u044c\u043d\u0430\u044f \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0438 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u044c \u0434\u0440\u0443\u0433\u0438\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u043e\u0442\u043b\u0438\u0447\u0430\u044e\u0442\u0441\u044f \u043e\u0442 \u043c\u0435\u0442\u043e\u0434\u0430 \u043a \u043c\u0435\u0442\u043e\u0434\u0443.<\/p>\n<p>  <\/p>\n<p>\u041e\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u043c\u0441\u044f \u043d\u0430 \u043c\u0435\u0442\u043e\u0434\u0435 <strong>LOUDS.<\/strong> \u041f\u043e\u043d\u044f\u0432 \u0435\u0433\u043e, \u043d\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u0442 \u0442\u0440\u0443\u0434\u0430 \u0440\u0430\u0437\u043e\u0431\u0440\u0430\u0442\u044c\u0441\u044f \u0441 \u0434\u0432\u0443\u043c\u044f \u0434\u0440\u0443\u0433\u0438\u043c\u0438. \u041a \u0442\u043e\u043c\u0443 \u0436\u0435, \u0432 \u043f\u0440\u043e\u0448\u043b\u043e\u043c \u0433\u043e\u0434\u0443 LOUDS-\u0434\u0435\u0440\u0435\u0432\u044c\u044f \u043e\u0442\u043c\u0435\u0442\u0438\u043b\u0438 \u0441\u0432\u043e\u0439 30-\u0439 \u044e\u0431\u0438\u043b\u0435\u0439! \u0414\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u043f\u043e\u043b\u0435\u0437\u043d\u044b\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438\u00a0\u0434\u043b\u044f LOUDS-\u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u044e\u0442\u0441\u044f \u0437\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/655\/b80\/5d6\/655b805d68b4b00a4e90f64eefbc6f1c.svg\" alt=\"$O(1)$\" data-tex=\"inline\"><\/math>: \u043d\u0430\u0439\u0442\u0438 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u0432 \u0443\u0437\u043b\u0430; \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u043d\u043e\u043c\u0435\u0440 \u043f\u043e\u0442\u043e\u043c\u043a\u0430 \u0443\u0437\u043b\u0430 \u0441\u0440\u0435\u0434\u0438 \u0432\u0441\u0435\u0445 \u0435\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u0432 (\u043f\u0435\u0440\u0432\u044b\u0439 \u043f\u043e\u0442\u043e\u043c\u043e\u043a, \u0432\u0442\u043e\u0440\u043e\u0439, <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math>-\u044b\u0439 \u0438 \u0442.\u0434.); \u043d\u0430\u0439\u0442\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math>-\u043e\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u0430. \u041d\u0435\u0434\u043e\u0441\u0442\u0430\u0442\u043e\u043a LOUDS \u2014 \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0438\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043f\u043e\u0434\u0441\u0447\u0435\u0442\u0430 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0443\u0437\u043b\u043e\u0432 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430.<\/p>\n<p>  <\/p>\n<p>\u0421\u0443\u0442\u044c \u043c\u0435\u0442\u043e\u0434\u0430 \u043f\u0440\u043e\u0441\u0442\u0430: \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u043a\u043b\u044e\u0447\u0438 \u0443\u0437\u043b\u043e\u0432 \u0434\u0435\u0440\u0435\u0432\u0430 \u0438 \u0432\u0441\u044e \u0446\u0435\u043d\u043d\u0443\u044e \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u0432 \u043e\u0431\u044b\u0447\u043d\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435, \u0430 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0434\u0435\u0440\u0435\u0432\u0430 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043a\u0430\u043a \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0431\u0438\u0442. \u0418\u0442\u043e\u0433\u043e \u0438\u043c\u0435\u0435\u043c \u0434\u0432\u0435 \u0441\u0442\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b. \u0417\u0430\u0442\u043e \u043d\u0435 \u043d\u0443\u0436\u043d\u043e \u0432\u044b\u0434\u0435\u043b\u044f\u0442\u044c \u043f\u0430\u043c\u044f\u0442\u044c \u043f\u043e\u0434 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0438 \u043d\u0430 \u0443\u0437\u043b\u044b \u0434\u0435\u0440\u0435\u0432\u0430: \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u044b \u043c\u0435\u0436\u0434\u0443 \u043d\u0438\u043c\u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u044b \u043f\u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0430\u043c \u0441 \u0430\u043a\u0442\u0438\u0432\u043d\u044b\u043c \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435\u043c rank\/select.<\/p>\n<p>  <\/p>\n<p>\u0412\u043d\u0438\u043c\u0430\u043d\u0438\u0435, \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e:<\/p>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/mz\/y9\/4i\/mzy94ipftwnhft_k1zix5wnrg9i.jpeg\" width=\"400\"><\/div>\n<p>  <\/p>\n<p><em>\u041f\u0440\u0435\u0444\u0438\u043a\u0441\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e, \u0433\u043e\u0442\u043e\u0432\u043e\u0435 \u043a \u0441\u0436\u0430\u0442\u0438\u044e \u043c\u0435\u0442\u043e\u0434\u043e\u043c LOUDS.<\/em><\/p>\n<p>  <\/p>\n<p>\u041f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u0438\u043c \u0434\u0435\u0440\u0435\u0432\u043e \u043a \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044e \u0432 \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u043c \u0432\u0438\u0434\u0435:<\/p>\n<p>  <\/p>\n<ol>\n<li>\u041f\u0440\u0438\u043a\u0440\u0435\u043f\u0438\u043c \u0434\u0435\u0440\u0435\u0432\u043e \u043a \u0444\u0435\u0439\u043a\u043e\u0432\u043e\u043c\u0443 \u043a\u043e\u0440\u043d\u044e. \u041e\u043d \u0441\u044b\u0433\u0440\u0430\u0435\u0442 \u0441\u0432\u043e\u044e \u0440\u043e\u043b\u044c \u0441\u043e\u0432\u0441\u0435\u043c \u0441\u043a\u043e\u0440\u043e.<\/li>\n<li>\u041f\u0440\u043e\u043d\u0443\u043c\u0435\u0440\u0443\u0435\u043c \u0432\u0441\u0435 \u0443\u0437\u043b\u044b \u0434\u0435\u0440\u0435\u0432\u0430\u00a0\u0443\u0440\u043e\u0432\u0435\u043d\u044c \u0437\u0430 \u0443\u0440\u043e\u0432\u043d\u0435\u043c \u0441\u043b\u0435\u0432\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043e, \u043a\u0430\u043a \u043f\u0440\u0438 BFS (\u043f\u043e\u0438\u0441\u043a\u0435 \u0432 \u0448\u0438\u0440\u0438\u043d\u0443).\u00a0\u0424\u0435\u0439\u043a\u043e\u0432\u044b\u0439 \u043a\u043e\u0440\u0435\u043d\u044c \u0438\u0433\u043d\u043e\u0440\u0438\u0440\u0443\u0435\u0442\u0441\u044f, \u0430 \u043d\u0430\u0441\u0442\u043e\u044f\u0449\u0438\u0439 \u0438\u043d\u0434\u0435\u043a\u0441\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043d\u0443\u043b\u0435\u043c.<\/li>\n<li>\u0417\u0430\u043a\u043e\u0434\u0438\u0440\u0443\u0435\u043c \u0443\u0437\u043b\u044b. \u0423\u0437\u0435\u043b \u0434\u0435\u0440\u0435\u0432\u0430 \u043a\u043e\u0434\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c\u044e \u0435\u0434\u0438\u043d\u0438\u0446, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u043c \u043f\u0440\u044f\u043c\u044b\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u0430\u043c, \u043f\u043b\u044e\u0441 \u043d\u043e\u043b\u044c. \u0415\u0441\u043b\u0438 \u0443 \u0443\u0437\u043b\u0430 \u0447\u0435\u0442\u044b\u0440\u0435 \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430, \u0442\u043e \u043e\u043d \u043a\u043e\u0434\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043a\u0430\u043a 11110, \u0430 \u0435\u0441\u043b\u0438 \u043d\u0438 \u043e\u0434\u043d\u043e\u0433\u043e \u2014 \u043a\u0430\u043a 0.\u00a0\u0424\u0435\u0439\u043a\u043e\u0432\u044b\u0439 \u043a\u043e\u0440\u0435\u043d\u044c \u043a\u043e\u0434\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0432 \u043f\u0435\u0440\u0432\u0443\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c. \u0423 \u043d\u0435\u0433\u043e \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0439 \u043f\u043e\u0442\u043e\u043c\u043e\u043a, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0435\u0433\u043e \u043a\u043e\u0434 10.<\/li>\n<\/ol>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/lp\/qm\/r3\/lpqmr36ehepgq1c2f059gp6ldba.jpeg\" width=\"450\"><\/div>\n<p>  <\/p>\n<p><em>\u041f\u0440\u0435\u0444\u0438\u043a\u0441\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u0441 \u043f\u0440\u043e\u043d\u0443\u043c\u0435\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u043c\u0438 \u043f\u043e \u0443\u0440\u043e\u0432\u043d\u044f\u043c \u0443\u0437\u043b\u0430\u043c\u0438. \u0423\u0437\u043b\u044b \u0437\u0430\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u044b.<\/em><\/p>\n<p>  <\/p>\n<p>\u0412 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u043f\u043e\u0443\u0440\u043e\u0432\u043d\u0435\u0432\u043e\u0433\u043e \u043e\u0431\u0445\u043e\u0434\u0430 \u0434\u0435\u0440\u0435\u0432\u0430 \u0444\u043e\u0440\u043c\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u044b\u0439 \u0438\u043d\u0434\u0435\u043a\u0441\u0438\u0440\u0443\u0435\u043c\u044b\u0439 \u0441\u043b\u043e\u0432\u0430\u0440\u044c \u2014 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0431\u0438\u0442 \u0438\u0437 \u0441\u043a\u043b\u0435\u0435\u043d\u043d\u044b\u0445 \u0441\u0432\u0435\u0440\u0445\u0443 \u0432\u043d\u0438\u0437 \u0438 \u0441\u043b\u0435\u0432\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043e \u0437\u0430\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432. \u0423 \u043d\u0430\u0441 \u044d\u0442\u043e 21-\u0431\u0438\u0442\u043d\u0430\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c. \u041a\u0441\u0442\u0430\u0442\u0438, \u043e\u043d\u0430 \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f\u00a0LBS (LOUDS Bit String).<\/p>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/wr\/vm\/mg\/wrvmmglftcnkt7kxqlsucgabj1u.jpeg\" width=\"600\"><\/div>\n<p>  <\/p>\n<p><em>\u041a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u044b\u0439 \u0438\u043d\u0434\u0435\u043a\u0441\u0438\u0440\u0443\u0435\u043c\u044b\u0439 \u0441\u043b\u043e\u0432\u0430\u0440\u044c \u0434\u043b\u044f \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430.<\/em><\/p>\n<p>  <\/p>\n<p>\u041a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u043e\u0435 \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e LOUDS \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u043e.\u00a0LBS \u0434\u043b\u044f \u0434\u0435\u0440\u0435\u0432\u0430 \u0441 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1e8\/0c3\/b30\/1e80c3b3087c0a57b68ad11261a9ec2b.svg\" alt=\"$N$\" data-tex=\"inline\"><\/math> \u0443\u0437\u043b\u0430\u043c\u0438 (\u0444\u0435\u0439\u043a\u043e\u0432\u044b\u0439 \u043d\u0435 \u0432 \u0441\u0447\u0435\u0442) \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/de0\/796\/ab9\/de0796ab921e53f64182aaf925faa731.svg\" alt=\"$2N+1$\" data-tex=\"inline\"><\/math> \u0431\u0438\u0442. \u041e\u0441\u0442\u0430\u043b\u043e\u0441\u044c \u0441\u0430\u043c\u043e\u0435 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0435 \u2014 \u0444\u043e\u0440\u043c\u0443\u043b\u044b \u0434\u043b\u044f \u043e\u0431\u0445\u043e\u0434\u0430 \u0434\u0435\u0440\u0435\u0432\u0430, \u043f\u0440\u0435\u0432\u0440\u0430\u0449\u0435\u043d\u043d\u043e\u0433\u043e \u0432 \u0431\u0438\u0442\u043e\u0432\u0443\u044e \u043a\u0430\u0440\u0442\u0443.<\/p>\n<p>  <\/p>\n<p><strong>\u041f\u043e\u0438\u0441\u043a \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u0430<\/strong>. \u041f\u0435\u0440\u0435\u0445\u043e\u0434 \u043e\u0442 \u0443\u0437\u043b\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math> \u043a \u0435\u0433\u043e \u043f\u0435\u0440\u0432\u043e\u043c\u0443 \u0434\u043e\u0447\u0435\u0440\u043d\u0435\u043c\u0443 \u0443\u0437\u043b\u0443 \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0435:<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/f8e\/c82\/779\/f8ec82779e653b0e480227a14dd40829.svg\" alt=\"$firstChild(i)= select_0(i + 1) - i$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math> \u2014 \u044d\u0442\u043e \u043d\u043e\u043c\u0435\u0440 \u0443\u0437\u043b\u0430, \u0432 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0439 \u0442\u0430\u0431\u043b\u0438\u0447\u043a\u0435 \u043f\u0440\u043e\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0439 \u0444\u0438\u043e\u043b\u0435\u0442\u043e\u0432\u044b\u043c. <\/p>\n<p>  <\/p>\n<p>\u041d\u0430\u0439\u0434\u0435\u043c \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u0430 \u0443\u0437\u043b\u0430 \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u043c 3 (\u0431\u0443\u043a\u0432\u0430 \u00ab\u0430\u00bb):<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d96\/a4d\/cbb\/d96a4dcbbe4b4ced0f0acc78b1370079.svg\" alt=\"$first\u0421hild(3) = select_0(3+1) - 3 = select_0(4) - 3 = 9 - 3 = 6$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u041f\u0435\u0440\u0432\u044b\u0439 \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0439 \u0443\u0437\u0435\u043b \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 6, \u0438 \u044d\u0442\u043e \u0431\u0443\u043a\u0432\u0430 \u00ab\u043a\u00bb.\u00a0\u041f\u0440\u0438\u043c\u0435\u043d\u0438\u043c \u0444\u043e\u0440\u043c\u0443\u043b\u0443 \u0434\u043b\u044f \u043a\u043e\u0440\u043d\u044f \u0434\u0435\u0440\u0435\u0432\u0430:<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/840\/80d\/17a\/84080d17a1d057aef8b73ff5e876d0ed.svg\" alt=\"$firstChild(0) = select_0(0+1) - 0 = select_0(1) = 1$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u041c\u044b \u043d\u0430\u0448\u043b\u0438 \u043b\u0438\u0441\u0442 \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u043c 1, \u0431\u0443\u043a\u0432\u0443 \u00ab\u0438\u00bb. \u0421\u0445\u043e\u0434\u0438\u0442\u0441\u044f! \u0421\u0442\u0430\u043b\u043e \u044f\u0441\u043d\u043e, \u0437\u0430\u0447\u0435\u043c \u043f\u043e\u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043b\u0441\u044f \u0444\u0435\u0439\u043a\u043e\u0432\u044b\u0439 \u043a\u043e\u0440\u0435\u043d\u044c: \u0434\u043b\u044f \u043c\u0430\u0433\u0438\u0438 \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u0446\u0438\u0438 \u0443\u0437\u043b\u043e\u0432. \u0412\u043e \u0438\u0437\u0431\u0435\u0436\u0430\u043d\u0438\u0435 \u0441\u0442\u0440\u0430\u043d\u043d\u044b\u0445 \u043e\u0448\u0438\u0431\u043e\u043a \u043f\u0435\u0440\u0435\u0434 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u043e\u043c \u043a \u043f\u043e\u0442\u043e\u043c\u043a\u0430\u043c \u0443\u0437\u043b\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math> \u043d\u0435\u043f\u043b\u043e\u0445\u043e \u0431\u044b \u0432\u044b\u044f\u0441\u043d\u0438\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u044d\u0442\u0438\u0445 \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u0432. \u0412\u0435\u0434\u044c \u0434\u043b\u044f \u043b\u0438\u0441\u0442\u044c\u0435\u0432 \u0434\u0435\u0440\u0435\u0432\u0430, \u0447\u0442\u043e \u043d\u0435 \u0443\u0434\u0438\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e, \u0444\u043e\u0440\u043c\u0443\u043b\u0430 \u0434\u0430\u0435\u0442 \u043d\u0435\u0430\u0434\u0435\u043a\u0432\u0430\u0442\u043d\u044b\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442. \u0427\u0442\u043e\u0431\u044b \u043d\u0430\u0439\u0442\u0438 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u0437\u0430 \u043f\u0435\u0440\u0432\u044b\u043c \u043f\u043e\u0442\u043e\u043c\u043a\u0430, \u043d\u0443\u0436\u043d\u043e \u043a \u0435\u0433\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 \u043f\u0440\u0438\u0431\u0430\u0432\u0438\u0442\u044c 1. \u042d\u0442\u043e \u043b\u043e\u0433\u0438\u0447\u043d\u043e, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u0438 \u043e\u0434\u043d\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0432\u0441\u0435\u0433\u0434\u0430 \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0440\u044f\u0434\u043e\u043c, \u0431\u0435\u0437 \u043f\u0440\u043e\u043c\u0435\u0436\u0443\u0442\u043a\u043e\u0432. \u041d\u043e \u043f\u0440\u0438 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u043f\u043e \u043d\u0438\u043c \u043d\u0443\u0436\u043d\u043e \u0432\u043e\u0432\u0440\u0435\u043c\u044f \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u044c\u0441\u044f \u2014 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c, \u043a\u0430\u043a\u043e\u0439 \u043f\u043e\u0442\u043e\u043c\u043e\u043a \u0441\u0447\u0438\u0442\u0430\u0435\u0442\u0441\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u043c.<\/p>\n<p>  <\/p>\n<p><strong>\u041f\u043e\u0438\u0441\u043a \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u0430<\/strong> \u0443\u0437\u043b\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math> \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u0442 \u0432 \u0434\u0432\u0430 \u044d\u0442\u0430\u043f\u0430: \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u0438\u043d\u0434\u0435\u043a\u0441\u0430 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0439 \u0435\u0434\u0438\u043d\u0438\u0446\u044b \u0432 \u043a\u043e\u0434\u0435 \u0443\u0437\u043b\u0430 \u2014 \u0438\u043c\u0435\u043d\u043d\u043e \u043e\u043d\u0430 \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442 \u0434\u0430\u043d\u043d\u043e\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u0430; \u0430 \u0437\u0430\u0442\u0435\u043c \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u0438\u043d\u0434\u0435\u043a\u0441\u0430 \u0441\u0430\u043c\u043e\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u0430:<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e32\/4ab\/db6\/e324abdb605edbe3e4666629de304836.svg\" alt=\"$lastChildPos(i) = select_0(i+2)-1$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u041f\u043e\u043b\u0443\u0447\u0438\u0432 \u0438\u043d\u0434\u0435\u043a\u0441 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0439 \u0435\u0434\u0438\u043d\u0438\u0446\u044b \u0432 \u043a\u043e\u0434\u0435 \u0443\u0437\u043b\u0430, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u0447\u0442\u043e \u0431\u0438\u0442 \u043f\u043e \u044d\u0442\u043e\u043c\u0443 \u0438\u043d\u0434\u0435\u043a\u0441\u0443 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d. \u0415\u0441\u043b\u0438 \u043d\u0435\u0442, \u0442\u043e \u0432\u044b\u0432\u043e\u0434 \u043d\u0430\u043f\u0440\u0430\u0448\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0441\u0430\u043c \u0441\u043e\u0431\u043e\u0439: \u044d\u0442\u043e \u0443\u0437\u0435\u043b \u0431\u0435\u0437 \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u0432, \u043b\u0438\u0441\u0442. \u0415\u0441\u043b\u0438 \u0436\u0435 \u0431\u0438\u0442 \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d, \u0442\u043e \u0434\u0435\u0439\u0441\u0442\u0432\u0443\u0435\u043c \u0434\u0430\u043b\u044c\u0448\u0435:<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/78c\/33c\/7d0\/78c33c7d039742dc11733d32457e9254.svg\" alt=\"$lastChild(i) = rank_1(lastChildPos(i)-1)$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u041d\u0430\u0439\u0434\u0435\u043c \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u0430 \u0443\u0437\u043b\u0430 2 (\u0431\u0443\u043a\u0432\u0430 \u00ab\u043a\u00bb).<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/cf3\/3ed\/f23\/cf33edf23ec6462d4e26eb330ec40771.svg\" alt=\"$lastChildPos(2) = select_0(2+2)-1=select_0(4)-1=9-1=8$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u0411\u0438\u0442 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 8 \u0440\u0430\u0432\u0435\u043d 1, \u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e, \u0443\u0437\u0435\u043b 2 \u2014 \u043d\u0435 \u043b\u0438\u0441\u0442, \u0438 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043d\u0430\u0439\u0442\u0438 \u0438\u043d\u0434\u0435\u043a\u0441 \u0435\u0433\u043e \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u0430:<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/570\/87f\/b85\/57087fb856345f661bf557981a15b4ce.svg\" alt=\"$lastChild(i) = rank_1(8-1)=5$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p><strong>\u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u0432.<\/strong> \u041f\u0440\u043e\u0441\u0442\u0435\u0439\u0448\u0438\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u0432 \u2014 \u0432\u044b\u0447\u0435\u0441\u0442\u044c \u0438\u0437 \u0438\u043d\u0434\u0435\u043a\u0441\u0430 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u0430 \u0443\u0437\u043b\u0430 \u0438\u043d\u0434\u0435\u043a\u0441 \u0435\u0433\u043e \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u0430 \u0438 \u043f\u0440\u0438\u0431\u0430\u0432\u0438\u0442\u044c 1:<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/def\/469\/8bb\/def4698bb4a85eb1821c0044c4c61c75.svg\" alt=\"$childrenCount(i) = last\u0421hild(i+1) - first\u0421hild(i)+1$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u041d\u043e \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c, \u0443 \u0443\u0437\u043b\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math> \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0439 \u0443\u0437\u0435\u043b <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b2d\/781\/41c\/b2d78141c2233ba9627a56bf0e895287.svg\" alt=\"$i+1$\" data-tex=\"inline\"><\/math>, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0440\u0430\u0441\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u0442\u043e\u043c \u0436\u0435 \u0443\u0440\u043e\u0432\u043d\u0435 \u0434\u0435\u0440\u0435\u0432\u0430, \u0447\u0442\u043e \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math>. \u0422\u043e\u0433\u0434\u0430 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u0432 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math> \u043c\u043e\u0436\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u043a\u0430\u043a \u0440\u0430\u0437\u043d\u043e\u0441\u0442\u044c \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u0432 \u043f\u0435\u0440\u0432\u044b\u0445 \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u0432 \u0443\u0437\u043b\u043e\u0432 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b2d\/781\/41c\/b2d78141c2233ba9627a56bf0e895287.svg\" alt=\"$i+1$\" data-tex=\"inline\"><\/math> \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math>:<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a8c\/b8c\/1d3\/a8cb8c1d3e64e3d69eb830b6af2d46d8.svg\" alt=\"$childrenCount(i) = first\u0421hild(i+1) - first\u0421hild(i)$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u041f\u043e\u0442\u043e\u043c\u043a\u0438 \u0443\u0437\u043b\u0430 \u0442\u0430\u043a\u0436\u0435 \u043f\u0440\u043e\u043d\u0443\u043c\u0435\u0440\u043e\u0432\u0430\u043d\u044b \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e. \u0415\u0441\u043b\u0438 \u043f\u0435\u0440\u0432\u044b\u0439 \u043f\u043e\u0442\u043e\u043c\u043e\u043a <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math> \u2014 \u044d\u0442\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b82\/8e2\/475\/b828e2475a3a56280b895f35eb250ea2.svg\" alt=\"$j$\" data-tex=\"inline\"><\/math>, \u0442\u043e \u0432\u0442\u043e\u0440\u043e\u0439 \u2014 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/02a\/a7d\/e38\/02aa7de38a957f1fb81ccc94010cceb3.svg\" alt=\"$j+1$\" data-tex=\"inline\"><\/math> \u0438 \u0442\u0430\u043a \u0434\u0430\u043b\u0435\u0435 \u0432\u043f\u043b\u043e\u0442\u044c \u0434\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u0430 \u0441\u043e\u0441\u0435\u0434\u043d\u0435\u0433\u043e \u043d\u0430 \u044d\u0442\u043e\u043c \u0443\u0440\u043e\u0432\u043d\u0435 \u0443\u0437\u043b\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b2d\/781\/41c\/b2d78141c2233ba9627a56bf0e895287.svg\" alt=\"$i+1$\" data-tex=\"inline\"><\/math> (\u0435\u0441\u043b\u0438 \u0442\u0430\u043a\u043e\u0432\u043e\u0439 \u0435\u0441\u0442\u044c).<\/p>\n<p>  <\/p>\n<p>\u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u0432 \u043b\u0438\u0441\u0442\u0430 \u00ab\u0438\u00bb \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u043c 1 \u043e\u0436\u0438\u0434\u0430\u0435\u043c\u043e \u043d\u0443\u043b\u0435\u0432\u043e\u0435:<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d29\/dc1\/dd9\/d29dc1dd9bf4f5f0b38a35ece61f93a8.svg\" alt=\"$childrenCount(1) =(select_0(2+1) - 2) - (select_0(1+1) - 1) = 3 - 3 = 0$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p><strong>\u041f\u043e\u0438\u0441\u043a \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f<\/strong> \u0434\u043b\u044f \u0443\u0437\u043b\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math> \u043e\u0440\u0433\u0430\u043d\u0438\u0437\u0443\u0435\u0442\u0441\u044f \u043f\u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0435:<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/ab1\/643\/387\/ab1643387ccaba85b4b2297bfbe4b4d8.svg\" alt=\"$parent(i) = rank_0(select_1(i+1) - 1) -1$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u0412\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u0435\u0439 \u0434\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u0443\u0437\u043b\u0430 6 (\u0431\u0443\u043a\u0432\u0430 \u00ab\u043a\u00bb):<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/0a6\/730\/02c\/0a673002cf57d4446e5284eacab4664a.svg\" alt=\"$parent(6) = rank_0(select_1(7) - 1) -1 = rank_0(9) -1 = 3$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u042d\u0442\u043e \u0443\u0437\u0435\u043b 3, \u0431\u0443\u043a\u0432\u0430 \u00ab\u0430\u00bb.<\/p>\n<p>  <\/p>\n<p>\u041e\u0431\u043b\u0430\u0434\u0430\u044f \u0437\u043d\u0430\u043d\u0438\u0435\u043c \u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0430\u0445 \u0434\u043b\u044f \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u0432 \u043f\u043e\u0442\u043e\u043c\u043a\u0430 \u0438 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f, \u043d\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u0442 \u0442\u0440\u0443\u0434\u0430 \u043e\u0431\u043e\u0439\u0442\u0438 \u0434\u0435\u0440\u0435\u0432\u043e \u0446\u0435\u043b\u0438\u043a\u043e\u043c. \u0413\u043b\u0430\u0432\u043d\u043e\u0435 \u2014 \u043d\u0435 \u0437\u0430\u0431\u044b\u0432\u0430\u0442\u044c \u043e\u0431 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0435 \u0433\u0440\u0430\u043d\u0438\u0447\u043d\u044b\u0445 \u0443\u0441\u043b\u043e\u0432\u0438\u0439 \u0434\u043b\u044f \u043a\u043e\u0440\u043d\u044f \u0438 \u043b\u0438\u0441\u0442\u044c\u0435\u0432.<\/p>\n<p>  <\/p>\n<p>\u041f\u0430\u0440\u0430 \u043a\u043e\u043f\u0435\u0435\u043a \u043f\u0440\u043e \u043c\u0435\u0442\u043e\u0434\u044b BP \u0438 DFUDS. \u0423 \u043e\u0431\u043e\u0438\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u0430\u044f \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u043a\u0430 \u2014 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/788\/906\/c12\/788906c124edd90129fbd06f990d3a43.svg\" alt=\"$2N + o(N)$\" data-tex=\"inline\"><\/math> \u0431\u0438\u0442 \u0434\u043b\u044f \u0434\u0435\u0440\u0435\u0432\u0430 \u0438\u0437 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1e8\/0c3\/b30\/1e80c3b3087c0a57b68ad11261a9ec2b.svg\" alt=\"$N$\" data-tex=\"inline\"><\/math> \u0443\u0437\u043b\u043e\u0432, \u0438 \u043e\u0431\u0430 \u043e\u043d\u0438 \u0441\u0445\u043e\u0436\u0438 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435\u043c \u0443\u0437\u043b\u0430 \u0434\u0435\u0440\u0435\u0432\u0430 \u0432 \u0432\u0438\u0434\u0435 \u043e\u0442\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0438\u0445 \u0438 \u0437\u0430\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0438\u0445 \u0441\u043a\u043e\u0431\u043e\u043a. <\/p>\n<p>  <\/p>\n<p><strong>BP<\/strong> (balanced parentheses) \u043a\u043e\u043d\u0432\u0435\u0440\u0442\u0438\u0440\u0443\u0435\u0442 \u0434\u0435\u0440\u0435\u0432\u043e \u0432 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0441\u043a\u043e\u0431\u043e\u043a, \u043f\u043e \u043f\u0430\u0440\u0435 \u043d\u0430 \u043a\u0430\u0436\u0434\u044b\u0439 \u0443\u0437\u0435\u043b. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u043e \u043e\u0431\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u0433\u043b\u0443\u0431\u0438\u043d\u0443; \u043a\u0430\u0436\u0434\u044b\u0439 \u0443\u0437\u0435\u043b \u043f\u043e\u0441\u0435\u0449\u0430\u0435\u0442\u0441\u044f \u0434\u0432\u0430\u0436\u0434\u044b. \u041f\u0440\u0438 \u043f\u0435\u0440\u0432\u043e\u043c \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u0438\u0438 \u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043e\u0442\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0430\u044f \u0441\u043a\u043e\u0431\u043a\u0430, \u043f\u0440\u0438 \u043f\u043e\u0432\u0442\u043e\u0440\u043d\u043e\u043c \u2014 \u0437\u0430\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0430\u044f. \u041c\u0435\u0436\u0434\u0443 \u043d\u0438\u043c\u0438 \u043e\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u0441\u043a\u043e\u0431\u043a\u0438 \u0434\u043e\u0447\u0435\u0440\u043d\u0438\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. <\/p>\n<p>  <\/p>\n<p>\u041f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0441\u043a\u043e\u0431\u043e\u043a \u0443\u0434\u043e\u0431\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432 \u0432\u0438\u0434\u0435 \u0431\u0438\u0442\u043e\u0432\u043e\u0439 \u043a\u0430\u0440\u0442\u044b, \u0433\u0434\u0435 1 \u2014 \u043e\u0442\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0430\u044f \u0441\u043a\u043e\u0431\u043a\u0430, \u0430 0 \u2014 \u0437\u0430\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0430\u044f. \u041d\u0430 \u0431\u044b\u0441\u0442\u0440\u044b\u0439 \u043f\u043e\u0438\u0441\u043a \u0432 \u043d\u0435\u0439 \u0437\u0430\u0442\u043e\u0447\u0435\u043d\u044b \u0432\u0441\u0435 \u0444\u043e\u0440\u043c\u0443\u043b\u044b \u0434\u043b\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0441 BP. \u0412 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 LOUDS, BP \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0431\u044b\u0441\u0442\u0440\u043e \u043f\u043e\u0434\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0440\u0430\u0437\u043c\u0435\u0440 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u0438 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u0433\u043e \u043e\u0431\u0449\u0435\u0433\u043e \u043f\u0440\u0435\u0434\u043a\u0430 \u0443 \u0434\u0432\u0443\u0445 \u0443\u0437\u043b\u043e\u0432. \u0410 \u0432\u043e\u0442 \u043d\u0430\u0439\u0442\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math>-\u043e\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u0430 \u0433\u043e\u0440\u0430\u0437\u0434\u043e \u0441\u043b\u043e\u0436\u043d\u0435\u0435, \u0447\u0435\u043c \u0432 LOUDS.<\/p>\n<p>  <\/p>\n<p><strong>DFUDS<\/strong> (depth-first unary degree sequence) \u0441\u0445\u043e\u0436 \u043e\u0434\u043d\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e \u0438 \u0441 BP, \u0438 \u0441 LOUDS. \u0421 BP \u0435\u0433\u043e \u043e\u0431\u044a\u0435\u0434\u0438\u043d\u044f\u0435\u0442 \u043e\u0431\u0445\u043e\u0434 \u0434\u0435\u0440\u0435\u0432\u0430 \u0432 \u0433\u043b\u0443\u0431\u0438\u043d\u0443 \u0438 \u0435\u0433\u043e \u0441\u043a\u043e\u0431\u043e\u0447\u043d\u043e\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435. \u0410 \u043f\u0440\u0438\u043d\u0446\u0438\u043f \u0440\u0430\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438 \u0441\u043a\u043e\u0431\u043e\u043a \u0442\u0430\u043a\u043e\u0439 \u0436\u0435, \u043a\u0430\u043a \u043f\u0440\u0438\u043d\u0446\u0438\u043f \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0443\u0437\u043b\u043e\u0432 \u0432 LOUDS. \u041f\u0435\u0440\u0435\u0434 \u043e\u0431\u0445\u043e\u0434\u043e\u043c \u0434\u0435\u0440\u0435\u0432\u0430 \u0437\u0430\u0440\u0430\u043d\u0435\u0435 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0432 \u0441\u043a\u043e\u0431\u043e\u0447\u043d\u0443\u044e \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043e\u0434\u043d\u0443 \u043e\u0442\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0443\u044e \u0441\u043a\u043e\u0431\u043a\u0443. \u041f\u043e\u0442\u043e\u043c \u043f\u0440\u0438 \u043e\u0431\u0445\u043e\u0434\u0435 \u0443\u0437\u043b\u043e\u0432 \u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c \u043e\u0442\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0438\u0435 \u0441\u043a\u043e\u0431\u043a\u0438 \u043f\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0443 \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u0432, \u043f\u043b\u044e\u0441 \u043e\u0434\u043d\u0443 \u0437\u0430\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0443\u044e. \u041f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u0432 \u0443 DFUDS \u0432\u044b\u0448\u0435, \u0447\u0435\u043c \u0443 BP. \u0412\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u0438 \u043f\u043e\u0438\u0441\u043a \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u0433\u043e \u043e\u0431\u0449\u0435\u0433\u043e \u043f\u0440\u0435\u0434\u043a\u0430 \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0437\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/655\/b80\/5d6\/655b805d68b4b00a4e90f64eefbc6f1c.svg\" alt=\"$O(1)$\" data-tex=\"inline\"><\/math>. \u0417\u0430\u0442\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u0432\u044b\u0441\u043e\u0442\u044b \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 \u0438 \u043f\u043e\u0438\u0441\u043a \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u043d\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b82\/8e2\/475\/b828e2475a3a56280b895f35eb250ea2.svg\" alt=\"$j$\" data-tex=\"inline\"><\/math>-\u043e\u043c \u0443\u0440\u043e\u0432\u043d\u0435 \u2014 \u0442\u044f\u0436\u0435\u043b\u044b\u0435 \u0434\u043b\u044f DFUDS \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438.<\/p>\n<p>  <\/p>\n<p>\u0414\u043b\u044f \u043d\u0430\u0433\u043b\u044f\u0434\u043d\u043e\u0441\u0442\u0438 \u0441\u0440\u0430\u0432\u043d\u0438\u043c \u043c\u0435\u0442\u043e\u0434\u044b LOUDS, BP \u0438 DFUDS \u043d\u0430 \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u043c\u0438\u043d\u0438-\u0434\u0435\u0440\u0435\u0432\u0430.<\/p>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/vw\/0t\/ny\/vw0tny0iapyww1n-lfrzhjawcrc.jpeg\" width=\"400\"><\/div>\n<p>  <\/p>\n<p><em>\u041e\u0440\u0430\u043d\u0436\u0435\u0432\u044b\u043c \u0446\u0432\u0435\u0442\u043e\u043c \u043f\u0440\u043e\u043d\u0443\u043c\u0435\u0440\u043e\u0432\u0430\u043d\u044b \u0443\u0437\u043b\u044b \u0434\u0435\u0440\u0435\u0432\u0430 \u043a\u0430\u043a \u043f\u0440\u0438 \u043e\u0431\u0445\u043e\u0434\u0435 \u0432 \u0448\u0438\u0440\u0438\u043d\u0443 (\u0434\u043b\u044f LOUDS), \u0441\u0438\u043d\u0438\u043c \u2014 \u043a\u0430\u043a \u043f\u0440\u0438 \u043e\u0431\u0445\u043e\u0434\u0435 \u0432 \u0433\u043b\u0443\u0431\u0438\u043d\u0443 (\u0434\u043b\u044f BP \u0438 DFUDS).<\/em><\/p>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/af\/7j\/e_\/af7je_qh_ngnl-rxaonpzayfazw.jpeg\" width=\"500\"><\/div>\n<p>  <\/p>\n<p><em>LOUDS, BP \u0438 DFUDS \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0434\u0435\u0440\u0435\u0432\u0430.<\/em><\/p>\n<p>  <\/p>\n<p>\u041d\u0435 \u0443\u0434\u0438\u0432\u043b\u044f\u0439\u0442\u0435\u0441\u044c, \u0435\u0441\u043b\u0438 \u0432 \u0430\u043d\u0433\u043b\u043e\u044f\u0437\u044b\u0447\u043d\u044b\u0445 \u0440\u0430\u0431\u043e\u0442\u0430\u0445 \u0443\u0432\u0438\u0434\u0438\u0442\u0435 \u043e\u0442\u043b\u0438\u0447\u0438\u044f \u0432 \u0444\u043e\u0440\u043c\u0443\u043b\u0430\u0445. \u0421\u0440\u0435\u0434\u0438 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u043e\u0432 \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u044e\u0442\u0441\u044f \u043b\u044e\u0431\u0438\u0442\u0435\u043b\u0438 \u0438\u043d\u0434\u0435\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 \u0435\u0434\u0438\u043d\u0438\u0446\u044b. \u0410 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a\u0438 \u0441\u0447\u0438\u0442\u0430\u044e\u0442 \u0441\u043b\u043e\u0432\u0430 rank \u0438 range \u0441\u043e\u0437\u0432\u0443\u0447\u043d\u044b\u043c\u0438, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0434\u0435\u043b\u0430\u044e\u0442 rank \u043d\u0430 \u043f\u043e\u043b\u0443\u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/394\/267\/4cc\/3942674cc140a867f6cb57b978965cf7.svg\" alt=\"$[0; i)$\" data-tex=\"inline\"><\/math>. \u0418\u0437-\u0437\u0430 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438 \u0441\u043e\u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u043e\u0441\u0442\u0438 rank\/select \u043e\u043d\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u044e\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1f9\/0ee\/550\/1f90ee550eb578f42bdd4a4aaeb58a2e.svg\" alt=\"$select(i)$\" data-tex=\"inline\"><\/math> \u043a\u0430\u043a <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/107\/02f\/6bd\/10702f6bd2d7ff85a2a5dc1644d2cb02.svg\" alt=\"$select(i+1)$\" data-tex=\"inline\"><\/math>. \u0417\u0430\u0442\u043e \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0444\u043e\u0440\u043c\u0443\u043b\u044b \u0432 \u0442\u0430\u043a\u043e\u043c \u0432\u0438\u0434\u0435 \u0432\u044b\u0433\u043b\u044f\u0434\u044f\u0442 \u043a\u043e\u0440\u043e\u0447\u0435.<\/p>\n<p>  <\/p>\n<h2 id=\"razrezhennyy-massiv-vzboltat-no-ne-smeshivat\">\u0420\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432: \u0432\u0437\u0431\u043e\u043b\u0442\u0430\u0442\u044c, \u043d\u043e \u043d\u0435 \u0441\u043c\u0435\u0448\u0438\u0432\u0430\u0442\u044c<\/h2>\n<p>  <\/p>\n<p>\u0420\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 (sparse array) \u2014 \u0435\u0449\u0435 \u043e\u0434\u043d\u0430 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430, \u0431\u0443\u043a\u0432\u0430\u043b\u044c\u043d\u043e \u0441\u043e\u0437\u0434\u0430\u043d\u043d\u0430\u044f \u0434\u043b\u044f \u0441\u0436\u0430\u0442\u0438\u044f. \u0420\u0430\u0437\u043c\u0435\u0440 \u0442\u0430\u043a\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u043f\u043e\u0440\u043e\u0439 \u043d\u0430 \u043f\u043e\u0440\u044f\u0434\u043a\u0438 \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u0435\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u043d\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. \u0410 \u043f\u0443\u0441\u0442\u044b\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043b\u0438\u0431\u043e \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u044e\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043f\u043e \u0443\u043c\u043e\u043b\u0447\u0430\u043d\u0438\u044e, \u043b\u0438\u0431\u043e \u043f\u043e\u043c\u0435\u0447\u0430\u044e\u0442\u0441\u044f \u0447\u0435\u043c-\u0442\u043e \u0432\u0440\u043e\u0434\u0435 null. \u0420\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \u043c\u0430\u044f\u0447\u0438\u0442 \u043d\u0430 \u0433\u043e\u0440\u0438\u0437\u043e\u043d\u0442\u0435 \u0432\u0441\u044f\u043a\u0438\u0439 \u0440\u0430\u0437 \u043f\u0440\u0438 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438 \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432 \u0438 \u0441\u0432\u044f\u0437\u0435\u0439 \u043c\u0435\u0436\u0434\u0443 \u043d\u0438\u043c\u0438. \u041d\u0430 \u0443\u043c \u0441\u0440\u0430\u0437\u0443 \u043f\u0440\u0438\u0445\u043e\u0434\u044f\u0442 \u0433\u0440\u0430\u0444\u044b \u0434\u0440\u0443\u0437\u0435\u0439 \u0432 \u0441\u043e\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0445 \u0441\u0435\u0442\u044f\u0445, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0440\u0430\u043d\u0436\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043f\u043e\u0438\u0441\u043a\u043e\u0432\u043e\u0439 \u0432\u044b\u0434\u0430\u0447\u0438, Excel-\u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0435 \u0442\u0430\u0431\u043b\u0438\u0446\u044b, \u0441\u0438\u043c\u0443\u043b\u044f\u0442\u043e\u0440\u044b \u044d\u043b\u0435\u043a\u0442\u0440\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0441\u0445\u0435\u043c \u0441 \u043c\u0438\u043b\u043b\u0438\u0430\u0440\u0434\u0430\u043c\u0438 \u0442\u0440\u0430\u043d\u0437\u0438\u0441\u0442\u043e\u0440\u043e\u0432 \u0432 \u0447\u0438\u043f\u0435. <\/p>\n<p>  <\/p>\n<p>\u0417\u0430\u0447\u0430\u0441\u0442\u0443\u044e \u0442\u0430\u043a\u0438\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u044b \u043f\u043e-\u043b\u0430\u0432\u043a\u0440\u0430\u0444\u0442\u043e\u0432\u0441\u043a\u0438 \u0446\u0438\u043a\u043b\u043e\u043f\u0438\u0447\u0435\u0441\u043a\u0438\u0435, \u043f\u0440\u0438 \u043d\u0430\u0438\u0432\u043d\u043e\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043d\u0435 \u0443\u043c\u0435\u0449\u0430\u044e\u0442\u0441\u044f \u0432 \u043e\u043f\u0435\u0440\u0430\u0442\u0438\u0432\u043a\u0443, \u043e\u0441\u0442\u0430\u0432\u0430\u044f\u0441\u044c \u0444\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u043d\u0435 \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u043d\u044b\u043c\u0438. \u0412 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u0439 \u043a \u043f\u0430\u043c\u044f\u0442\u0438 \u0438 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u0438 \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u044b\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u044b \u043f\u0440\u0435\u0432\u0440\u0430\u0449\u0430\u044e\u0442 \u0432 \u043a\u0443\u0434\u0430 \u0431\u043e\u043b\u0435\u0435 \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u044b\u0435 \u0445\u044d\u0448-\u0442\u0430\u0431\u043b\u0438\u0446\u044b, \u0441\u043f\u0438\u0441\u043a\u0438 \u0441\u043c\u0435\u0436\u043d\u043e\u0441\u0442\u0438, \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u0435 \u0434\u0435\u0440\u0435\u0432\u044c\u044f\u2026 \u0438\u043b\u0438 \u043f\u043e\u0434\u0432\u0435\u0440\u0433\u0430\u044e\u0442 succinct&#8217;\u0438\u0437\u0430\u0446\u0438\u0438.<\/p>\n<p>  <\/p>\n<p>\u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c, \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \u0441\u0442\u0440\u043e\u043a. \u041f\u0440\u0438\u0446\u0435\u043f\u0438\u043c \u043a \u043d\u0435\u043c\u0443 \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u044b\u0439 \u0438\u043d\u0434\u0435\u043a\u0441\u0438\u0440\u0443\u0435\u043c\u044b\u0439 \u0441\u043b\u043e\u0432\u0430\u0440\u044c. \u0427\u0442\u043e \u044d\u0442\u043e \u0434\u0430\u0441\u0442? <\/p>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/lq\/b3\/g9\/lqb3g9tpjmvdh7guqdohhpcjqgy.jpeg\" width=\"450\"><\/div>\n<p>  <\/p>\n<p><em>\u0420\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \u0441 \u0431\u0438\u0442\u043e\u0432\u043e\u0439 \u043a\u0430\u0440\u0442\u043e\u0439.<\/em><\/p>\n<p>  <\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c, \u043d\u0435 \u043e\u0431\u0440\u0430\u0449\u0430\u044f\u0441\u044c \u043a \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u043c\u0443 \u043c\u0430\u0441\u0441\u0438\u0432\u0443 \u043d\u0430\u043f\u0440\u044f\u043c\u0443\u044e, \u043b\u0435\u0433\u043a\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u043f\u0440\u0438\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u043b\u0438 \u0432 \u043d\u0435\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043f\u043e \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u0443\u044e\u0449\u0435\u043c\u0443 \u0438\u043d\u0434\u0435\u043a\u0441\u0443. \u041d\u0438\u0447\u0442\u043e \u043d\u0435 \u043c\u0435\u0448\u0430\u0435\u0442 \u0443\u0436\u0430\u0442\u044c \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432, \u0432\u044b\u043a\u0438\u043d\u0443\u0432 \u0432\u0441\u0435 \u043d\u0435 \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u043d\u044b\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b:<\/p>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/g7\/ol\/7t\/g7ol7tgfr8xup1ijubai1zjqgm8.jpeg\" width=\"350\"><\/div>\n<p>  <\/p>\n<p><em>\u041c\u0430\u0441\u0441\u0438\u0432 \u0431\u0435\u0437 \u043f\u0443\u0441\u0442\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432.<\/em><\/p>\n<p>  <\/p>\n<p><strong>\u0412\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u0438\u043d\u0434\u0435\u043a\u0441\u0430 \u0432 \u0441\u0436\u0430\u0442\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435.<\/strong> \u041f\u043e\u0441\u043b\u0435 \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u043f\u0440\u0438\u0441\u0443\u0442\u0441\u0442\u0432\u0438\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043d\u0435\u043f\u043b\u043e\u0445\u043e \u0431\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0434\u043e\u0441\u0442\u0443\u043f \u043a \u0435\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044e \u0432 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435, \u0442\u043e \u0435\u0441\u0442\u044c \u0441\u043e\u043f\u043e\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0438\u043d\u0434\u0435\u043a\u0441 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math> \u0432 \u0438\u043d\u0434\u0435\u043a\u0441\u0438\u0440\u0443\u0435\u043c\u043e\u043c \u0441\u043b\u043e\u0432\u0430\u0440\u0435 \u0438\u043d\u0434\u0435\u043a\u0441\u0443 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b82\/8e2\/475\/b828e2475a3a56280b895f35eb250ea2.svg\" alt=\"$j$\" data-tex=\"inline\"><\/math> \u0432 \u0441\u0436\u0430\u0442\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435. \u041d\u0435 \u0441\u044e\u0440\u043f\u0440\u0438\u0437, \u0447\u0442\u043e \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f rank:<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/56e\/bf9\/88c\/56ebf988c1663bdaf7670919b511dfd0.svg\" alt=\"$j = rank_1(i) -1$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u041f\u0440\u043e\u0432\u0435\u0440\u0438\u043c, \u043a\u0430\u043a \u043e\u0431\u0441\u0442\u043e\u044f\u0442 \u0434\u0435\u043b\u0430 \u0441 8-\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c: <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a08\/8f2\/3cf\/a088f23cfe7961e936a53e07ad19f784.svg\" alt=\"$bitmap[8] = 0$\" data-tex=\"inline\"><\/math>. \u0417\u043d\u0430\u0447\u0438\u0442, \u0432 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u0442\u0430\u043a\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043d\u0435\u0442. \u0410 \u0447\u0442\u043e \u0441 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c 7? <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a9a\/bff\/4bc\/a9abff4bcc30acf06b2ca122d5962375.svg\" alt=\"$bitmap[7] = 1$\" data-tex=\"inline\"><\/math>. \u041f\u043e\u043b\u0443\u0447\u0438\u043c \u0435\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435: <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/4a3\/859\/9ef\/4a38599ef9bcdb95cfe43d81504a9b82.svg\" alt=\"$rank_1(7) - 1 = 3-1 = 2$\" data-tex=\"inline\"><\/math>. \u041f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 2 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u00abgo\u00bb. <\/p>\n<p>  <\/p>\n<p><strong>\u0412\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u0438\u043d\u0434\u0435\u043a\u0441\u0430 \u0432 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435.<\/strong> \u041d\u0430\u0432\u0435\u0440\u043d\u044f\u043a\u0430 \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0438\u0441\u043a\u0430\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043f\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044e! \u0415\u0441\u043b\u0438 \u0434\u0430\u043d\u043d\u044b\u0435 \u043d\u0435 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u044b, \u043f\u043e\u0438\u0441\u043a \u0441\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u043a \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0443 \u0437\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/11b\/bac\/909\/11bbac909816a3563f0b61feec7a26f4.svg\" alt=\"$O(N)$\" data-tex=\"inline\"><\/math>, \u0433\u0434\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1e8\/0c3\/b30\/1e80c3b3087c0a57b68ad11261a9ec2b.svg\" alt=\"$N$\" data-tex=\"inline\"><\/math> \u2014 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043d\u0435 \u043f\u0443\u0441\u0442\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. \u0414\u043b\u044f \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b82\/8e2\/475\/b828e2475a3a56280b895f35eb250ea2.svg\" alt=\"$j$\" data-tex=\"inline\"><\/math> \u043c\u043e\u0436\u0435\u0442 \u043f\u043e\u0442\u0440\u0435\u0431\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0435\u0433\u043e \u0438\u043d\u0434\u0435\u043a\u0441 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math>, \u043a\u0430\u043a \u0435\u0441\u043b\u0438 \u0431\u044b \u043c\u0430\u0441\u0441\u0438\u0432 \u043d\u0435 \u0431\u044b\u043b \u0443\u0436\u0430\u0442. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f select \u2014 \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u0439 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0435\u0439 \u043a rank:<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/230\/17c\/5c7\/23017c5c708d28ce1ed9e5a875a83a13.svg\" alt=\"$i = select_1(j+1)$\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u0414\u043b\u044f \u043f\u0440\u0438\u043c\u0435\u0440\u0430 \u043e\u0442\u044b\u0449\u0435\u043c \u0441\u0442\u0440\u043e\u043a\u0443 \u00abC++\u00bb. \u0412 \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u043e\u043d\u0430 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 0. \u0410 \u0435\u0435 \u0438\u043d\u0434\u0435\u043a\u0441 \u0432 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u0440\u0430\u0432\u0435\u043d <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d59\/430\/166\/d594301660be9ebc941020a10016964d.svg\" alt=\"$select_1(0+1) = 3$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  <\/p>\n<p>\u0423\u0436\u0435 \u043d\u0430 \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u0441\u043e \u0441\u0442\u0440\u043e\u043a\u0430\u043c\u0438 \u0437\u0430\u043c\u0435\u0442\u043d\u0430 \u044d\u043a\u043e\u043d\u043e\u043c\u0438\u044f \u043f\u0430\u043c\u044f\u0442\u0438. \u0415\u0441\u043b\u0438 \u043c\u0430\u0441\u0441\u0438\u0432 \u043f\u0440\u0435\u0434\u043d\u0430\u0437\u043d\u0430\u0447\u0435\u043d \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043a\u043b\u0430\u0441\u0441\u043e\u0432 \u0441\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e\u043c \u043f\u043e\u043b\u0435\u0439, \u044d\u043a\u043e\u043d\u043e\u043c\u0438\u044f \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043a\u0443\u0434\u0430 \u0432\u0435\u0441\u043e\u043c\u0435\u0435. \u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, \u043f\u043e\u0438\u0441\u043a \u0432 \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0431\u044b\u0441\u0442\u0440\u0435\u0435, \u0447\u0435\u043c \u0432 \u0431\u043e\u043b\u044c\u0448\u043e\u043c \u0438 \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u043e\u043c: \u043e\u043d \u043b\u0443\u0447\u0448\u0435 \u043a\u044d\u0448\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u043e\u043c. \u0423 \u0431\u0438\u0442\u043e\u0432\u043e\u0433\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0438\u0440\u0443\u0435\u043c\u043e\u0433\u043e \u0441\u043b\u043e\u0432\u0430\u0440\u044f \u0431\u043e\u043b\u044c\u0448\u0435 \u0448\u0430\u043d\u0441\u043e\u0432 \u0443\u043c\u0435\u0441\u0442\u0438\u0442\u044c\u0441\u044f \u0432 \u043a\u044d\u0448-\u043b\u0438\u043d\u0438\u044e, \u0447\u0435\u043c \u0443 \u043e\u0431\u044b\u0447\u043d\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0447\u0438\u0441\u0435\u043b, \u0441\u0442\u0440\u043e\u043a \u0438\u043b\u0438 \u043d\u0430\u0432\u043e\u0440\u043e\u0447\u0435\u043d\u043d\u044b\u0445 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u0441\u043a\u0438\u0445 \u0442\u0438\u043f\u043e\u0432.<\/p>\n<p>  <\/p>\n<p>\u041a\u043e\u043d\u0435\u0447\u043d\u043e, \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/42d\/b5e\/0d1\/42db5e0d1d343213c6bb1cd91ccb8289.svg\" alt=\"$2^{30}$\" data-tex=\"inline\"><\/math> \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043e\u043f\u0438\u0441\u0430\u043d\u043d\u044b\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u043d\u0435 \u0433\u043e\u0434\u0438\u0442\u0441\u044f. \u0415\u0433\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c\u043e\u0441\u0442\u044c \u0437\u0430\u043a\u0430\u043d\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0442\u0430\u043c, \u0433\u0434\u0435 \u043d\u0430\u0447\u0438\u043d\u0430\u044e\u0442\u0441\u044f \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u0441 \u0440\u0430\u0437\u0440\u0430\u0441\u0442\u0430\u043d\u0438\u0435\u043c \u0438\u043d\u0434\u0435\u043a\u0441\u0430. \u041d\u043e \u0441\u0432\u043e\u044f \u043d\u0438\u0448\u0430 \u0443 \u044d\u0442\u043e\u0433\u043e \u0441\u043f\u043e\u0441\u043e\u0431\u0430 \u0441\u0436\u0430\u0442\u0438\u044f \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432 \u0438 \u0435\u0433\u043e \u0432\u0430\u0440\u0438\u0430\u0446\u0438\u0439, \u043a\u043e\u043d\u0435\u0447\u043d\u043e, \u0435\u0441\u0442\u044c. \u0411\u0443\u0434\u043d\u0438\u0447\u043d\u044b\u0439 \u043f\u0440\u0438\u043c\u0435\u0440 \u2014 \u044d\u0442\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043f\u0440\u043e\u0442\u043e\u043a\u043e\u043b\u0430 BitTorrent. \u0411\u0438\u0442\u043e\u0432\u0430\u044f \u043a\u0430\u0440\u0442\u0430 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u043e \u0441\u043a\u0430\u0447\u0430\u043d\u043d\u044b\u0445 \u0441\u0435\u0433\u043c\u0435\u043d\u0442\u0430\u0445 \u0444\u0430\u0439\u043b\u043e\u0432, \u0438 \u043f\u0438\u0440\u044b \u043e\u0431\u043c\u0435\u043d\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c\u0438 \u0438\u043c\u0435\u044e\u0449\u0438\u0445\u0441\u044f \u0443 \u043d\u0438\u0445 \u0441\u0435\u0433\u043c\u0435\u043d\u0442\u043e\u0432. \u041a\u043e\u0441\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u043f\u0440\u0438\u043c\u0435\u0440 \u2014 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b \u0441\u0435\u0433\u043c\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u043f\u0435\u0440\u0435\u0434\u0430\u0447\u0438 \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442 \u043c\u0430\u0440\u0441\u043e\u0445\u043e\u0434\u044b, \u0412\u043e\u044f\u0434\u0436\u0435\u0440\u044b \u0438 \u0441\u0442\u0430\u043d\u0446\u0438\u044f \u00ab\u041d\u043e\u0432\u044b\u0435 \u0413\u043e\u0440\u0438\u0437\u043e\u043d\u0442\u044b\u00bb, \u0431\u043e\u0440\u043e\u0437\u0434\u044f\u0449\u0430\u044f \u0442\u0440\u0430\u043d\u0441\u043d\u0435\u043f\u0442\u0443\u043d\u043e\u0432\u044b\u0435 \u043f\u0440\u043e\u0441\u0442\u043e\u0440\u044b.<\/p>\n<p>  <\/p>\n<p>\u041e\u043f\u0438\u0441\u0430\u043d\u043d\u044b\u0435 \u043f\u0440\u0438\u043c\u0435\u0440\u044b succinct&#8217;\u0438\u0437\u0430\u0446\u0438\u0438 \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u0438 \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u044b \u043d\u0430 \u043e\u0431\u0449\u0435\u043c \u0444\u0443\u043d\u0434\u0430\u043c\u0435\u043d\u0442\u0435. \u041e\u043d \u043e\u0441\u043d\u043e\u0432\u0430\u043d \u043d\u0430 \u043d\u0435\u0441\u043e\u043a\u0440\u0443\u0448\u0438\u043c\u043e\u0439 \u0432\u0435\u0440\u0435 \u0432 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u044c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 rank\/select. \u0411\u0435\u0437 \u043d\u0435\u0435 \u0432\u0441\u044f \u0442\u0435\u043e\u0440\u0438\u044f \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u044b\u0445, \u043d\u043e \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0431\u044b\u0441\u0442\u0440\u044b\u0445 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u0442\u0440\u0435\u0449\u0438\u0442 \u043f\u043e \u0448\u0432\u0430\u043c. \u041e\u0442 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u0438 rank \u0438 select \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u0430\u0434\u0435\u043a\u0432\u0430\u0442\u043d\u043e\u0441\u0442\u044c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u044b\u0445 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u0437\u0430 \u043f\u0440\u0435\u0434\u0435\u043b\u0430\u043c\u0438 \u0434\u0438\u0441\u0441\u0435\u0440\u0442\u0430\u0446\u0438\u0439.<\/p>\n<p>  <\/p>\n<p>\u042d\u0442\u0438 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0432 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435 \u043c\u043e\u0436\u043d\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043a\u0440\u0430\u0439\u043d\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e: rank \u2014 \u0437\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/655\/b80\/5d6\/655b805d68b4b00a4e90f64eefbc6f1c.svg\" alt=\"$O(1)$\" data-tex=\"inline\"><\/math>; select \u2014 \u0437\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6cb\/ea2\/258\/6cbea225882d7eddb455a3c64f53d402.svg\" alt=\"$O(lg (lg N))$\" data-tex=\"inline\"><\/math>, \u0447\u0442\u043e \u0442\u043e\u0436\u0435 \u043f\u043e\u0447\u0442\u0438 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0430. \u0418 \u043a\u043e\u043d\u0435\u0447\u043d\u043e \u0431\u0435\u0437 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0443\u043b\u043e\u0432\u043e\u043a \u043d\u0435 \u043e\u0431\u043e\u0439\u0434\u0435\u0442\u0441\u044f. \u0410 \u0442\u0430\u043a \u043a\u0430\u043a \u0432 \u043b\u044e\u0431\u043e\u043c \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0438 \u0441 \u0437\u0430\u043f\u0443\u0442\u0430\u043d\u043d\u044b\u043c \u0441\u044e\u0436\u0435\u0442\u043e\u043c \u0434\u043e\u043b\u0436\u043d\u0430 \u0432\u0438\u0442\u0430\u0442\u044c \u043b\u0435\u0433\u043a\u0430\u044f \u043d\u0435\u0434\u043e\u0441\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u0441\u0442\u044c, \u043d\u0430 \u044d\u0442\u043e\u043c \u044f \u0438 \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u044e\u0441\u044c.<\/p>\n<p>  <\/p>\n<h2 id=\"interesnye-fakty\">\u0418\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u0435 \u0444\u0430\u043a\u0442\u044b<\/h2>\n<p>  <\/p>\n<p><strong>\u0427\u0442\u043e \u0442\u0430\u043a\u043e\u0435 \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u043d\u0438\u0436\u043d\u044f\u044f \u0433\u0440\u0430\u043d\u0438\u0446\u0430 \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u043c\u044b\u0445 \u0440\u0435\u0441\u0443\u0440\u0441\u043e\u0432 \u0441 \u0442\u043e\u0447\u043a\u0438 \u0437\u0440\u0435\u043d\u0438\u044f \u0442\u0435\u043e\u0440\u0438\u0438 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438?<\/strong> \u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c, \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u0445\u0440\u0430\u043d\u0438\u0442 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0438\u0437 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1e8\/0c3\/b30\/1e80c3b3087c0a57b68ad11261a9ec2b.svg\" alt=\"$N$\" data-tex=\"inline\"><\/math> \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. \u0427\u0442\u043e\u0431\u044b \u0438\u0434\u0435\u043d\u0442\u0438\u0444\u0438\u0446\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0438\u0445 \u0431\u0435\u0437 \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u0439, \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0438\u0442, \u043d\u0435 \u043c\u0435\u043d\u044c\u0448\u0435\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d2d\/9d9\/112\/d2d9d9112f37d46e610a838438eb2516.svg\" alt=\"$X=log_2N$\" data-tex=\"inline\"><\/math>. <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6d6\/a4f\/78f\/6d6a4f78fbacd6edecc018ce8ad3e364.svg\" alt=\"$X$\" data-tex=\"inline\"><\/math> \u0438 \u0435\u0441\u0442\u044c \u0442\u0430 \u0441\u0430\u043c\u0430\u044f \u043d\u0438\u0436\u043d\u044f\u044f \u0433\u0440\u0430\u043d\u0438\u0446\u0430, \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u0430\u044f \u043f\u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0435 \u0425\u0430\u0440\u0442\u043b\u0438. \u0412 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0447\u0430\u0441\u0442\u043d\u044b\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445, \u043e\u0431\u043b\u0430\u0434\u0430\u044f \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0435\u0439 \u043e \u043f\u0440\u0438\u0440\u043e\u0434\u0435 \u0445\u0440\u0430\u043d\u0438\u043c\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445, \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0443\u0434\u0430\u0435\u0442\u0441\u044f \u0443\u0436\u0430\u0442\u044c \u0435\u0449\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u0435\u0435.<\/p>\n<p>  <\/p>\n<p><strong>\u0421\u0447\u0438\u0442\u0430\u0435\u0442\u0441\u044f \u043b\u0438 \u0441\u0438\u0448\u043d\u0430\u044f \u0441\u0442\u0440\u043e\u043a\u0430 succinct \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u043e\u0439 \u0434\u0430\u043d\u043d\u044b\u0445?<\/strong> \u041e\u043d\u0430 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1e8\/0c3\/b30\/1e80c3b3087c0a57b68ad11261a9ec2b.svg\" alt=\"$N$\" data-tex=\"inline\"><\/math> \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0438 \u0437\u0430\u0432\u0435\u0440\u0448\u0430\u0435\u0442\u0441\u044f \u043d\u0443\u043b\u0435\u0432\u044b\u043c \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u043c ASCII. \u0417\u043d\u0430\u0447\u0438\u0442, \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e85\/f9c\/8cc\/e85f9c8cc3824642e2d877991b105d33.svg\" alt=\"$N+1$\" data-tex=\"inline\"><\/math> \u043c\u0435\u0441\u0442\u0430, \u0438 \u043f\u043e\u044d\u0442\u043e\u043c\u0443\u2026 \u043e\u043d\u0430 succinct, \u0430 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u0435\u0435, implicit! \u0427\u0442\u043e \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442 \u043d\u0430\u0441 \u043a \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c\u0443 \u0432\u043e\u043f\u0440\u043e\u0441\u0443.<\/p>\n<p>  <\/p>\n<p><strong>\u0412\u0441\u0435 \u043b\u0438 succinct \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u043e \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u044b?<\/strong> \u041e\u0431\u043b\u0430\u0441\u0442\u044c \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f succinct \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442 \u0430\u0436 \u0442\u0440\u0438 \u0432\u0438\u0434\u0430 \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u044b\u0445 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440, \u0440\u0430\u0437\u043b\u0438\u0447\u0430\u044e\u0449\u0438\u0445\u0441\u044f \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c\u044e:<\/p>\n<p>  <\/p>\n<ul>\n<li>compact \u2014 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/11b\/bac\/909\/11bbac909816a3563f0b61feec7a26f4.svg\" alt=\"$O(N)$\" data-tex=\"inline\"><\/math>. \u041b\u0438\u043d\u0435\u0439\u043d\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043e\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1e8\/0c3\/b30\/1e80c3b3087c0a57b68ad11261a9ec2b.svg\" alt=\"$N$\" data-tex=\"inline\"><\/math> \u2014 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0445\u0440\u0430\u043d\u0438\u043c\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. \u0421\u0430\u043c\u044b\u0435 \u00ab\u0445\u0430\u043b\u044f\u0432\u043d\u044b\u0435\u00bb \u0432 \u043f\u043b\u0430\u043d\u0435 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u0439 \u043a \u0441\u0436\u0430\u0442\u0438\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b. \u0422\u0430\u043a \u0441\u043a\u0430\u0437\u0430\u0442\u044c \u0440\u0430\u0437\u043c\u0438\u043d\u043a\u0430 \u043f\u0435\u0440\u0435\u0434 \u043d\u0430\u0441\u0442\u043e\u044f\u0449\u0438\u043c \u0445\u0430\u0440\u0434\u043a\u043e\u0440\u043e\u043c. \u0415\u0441\u043b\u0438 \u0443\u0436 \u043c\u044b \u0437\u0430\u0433\u043e\u0432\u043e\u0440\u0438\u043b\u0438 \u043f\u0440\u043e \u0441\u0442\u0440\u043e\u043a\u0438, \u0442\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u0438\u0442 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u043f\u0440\u0438\u043c\u0435\u0440: \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0441\u0442\u0440\u043e\u043a \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b. \u0421\u0442\u0440\u043e\u043a\u0438 \u0445\u0440\u0430\u043d\u044f\u0442\u0441\u044f \u043e\u0434\u043d\u0430 \u0437\u0430 \u0434\u0440\u0443\u0433\u043e\u0439, \u0431\u0435\u0437\u043e \u0432\u0441\u044f\u043a\u0438\u0445 \u0440\u0430\u0437\u0434\u0435\u043b\u0438\u0442\u0435\u043b\u0435\u0439. \u0414\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0445 \u0441\u0442\u0440\u043e\u043a \u0444\u043e\u0440\u043c\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0431\u0438\u0442\u043e\u0432\u0430\u044f \u043a\u0430\u0440\u0442\u0430, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0432\u0441\u0435 \u0431\u0438\u0442\u044b \u0441\u0431\u0440\u043e\u0448\u0435\u043d\u044b \u0432 0 \u043a\u0440\u043e\u043c\u0435 \u0431\u0438\u0442\u043e\u0432 \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c\u0438, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u043c\u0438 \u043d\u0430\u0447\u0430\u043b\u0430\u043c \u0441\u0442\u0440\u043e\u043a. \u042d\u0442\u0430 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/f2b\/daa\/54a\/f2bdaa54a77e711bb2a518b71261c68a.svg\" alt=\"$O(2N)$\" data-tex=\"inline\"><\/math> (\u043c\u043d\u043e\u0436\u0438\u0442\u0435\u043b\u044c 2 \u043f\u0440\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0438 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u041b\u0430\u043d\u0434\u0430\u0443 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u0435\u0435 \u0432\u0441\u0435\u0433\u043e \u043e\u043f\u0443\u0441\u0442\u0438\u0442\u044c, \u043d\u043e \u0442\u0430\u043a \u043d\u0430\u0433\u043b\u044f\u0434\u043d\u0435\u0435) \u0438 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0431\u044b\u0441\u0442\u0440\u044b\u0439 select \u0434\u043b\u044f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u043a\u0430\u0436\u0434\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0438 \u0432 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438.<\/li>\n<li>succinct \u2014 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/98a\/45f\/820\/98a45f8209b6a84b826b9398ee0ddd9f.svg\" alt=\"$N + o(N)$\" data-tex=\"inline\"><\/math>. \u0421\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0441 \u044d\u0442\u043e\u0439 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c\u044e \u2014 \u0442\u043e, \u0447\u0442\u043e \u0438\u043c\u0435\u0435\u0442\u0441\u044f \u0432\u0432\u0438\u0434\u0443 \u043f\u043e\u0434 succinct data structures \u043f\u043e \u0443\u043c\u043e\u043b\u0447\u0430\u043d\u0438\u044e. \u041f\u0440\u0438\u043c\u0435\u0440 \u0438\u0437 \u043c\u0438\u0440\u0430 \u0441\u0442\u0440\u043e\u043a: \u0441\u0442\u0440\u043e\u043a\u0438 \u043d\u0430\u043f\u043e\u0434\u043e\u0431\u0438\u0435 \u043f\u0430\u0441\u043a\u0430\u043b\u0435\u0432\u0441\u043a\u0438\u0445 (Pascal string), \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u043f\u0440\u0435\u0434\u0432\u0430\u0440\u044f\u0435\u0442\u0441\u044f \u0438\u0445 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e\u043c. \u041e\u043d\u0438 \u0437\u0430\u043d\u0438\u043c\u0430\u044e\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a93\/685\/5ae\/a936855aed1f0dc8d857c7b21acc1430.svg\" alt=\"$N + log(N)$\" data-tex=\"inline\"><\/math>.<\/li>\n<li>implicit \u2014 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/224\/836\/655\/2248366553f4c9435df0dd8e9560ed92.svg\" alt=\"$N + O(1)$\" data-tex=\"inline\"><\/math>. \u0421\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b, \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0449\u0438\u0435 \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0430\u043c\u044f\u0442\u0438. \u041f\u0440\u0438\u043c\u0435\u0440\u044b: \u043a\u0443\u0447\u0430 (heap) \u0438 \u0441\u0438\u0448\u043d\u0430\u044f \u0441\u0442\u0440\u043e\u043a\u0430. \u041e\u0431\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0437\u0430\u043d\u0438\u043c\u0430\u044e\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e85\/f9c\/8cc\/e85f9c8cc3824642e2d877991b105d33.svg\" alt=\"$N + 1$\" data-tex=\"inline\"><\/math>.<\/li>\n<\/ul>\n<p>  <\/p>\n<p><strong>\u041a\u0430\u043a\u0438\u0435 \u0435\u0449\u0435 \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u044b\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435?<\/strong> \u0412 \u0441\u043c\u044b\u0441\u043b\u0435, \u043d\u0435 \u0434\u043b\u044f \u043d\u0430\u0443\u0447\u043d\u044b\u0445 \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0439 \u043f\u043e \u043f\u043b\u0430\u043d\u0443 \u043a\u0430\u0444\u0435\u0434\u0440\u044b, \u0430 \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043e\u0431\u043a\u0430\u0442\u0430\u043d\u043d\u044b\u0445 \u0431\u043e\u0435\u0432\u044b\u0445 \u0440\u0435\u0448\u0435\u043d\u0438\u0439. \u0412 \u0441\u0442\u0430\u0442\u044c\u0435 \u0440\u0435\u0447\u044c \u0448\u043b\u0430 \u043f\u0440\u043e succinct-\u043f\u0440\u0435\u0444\u0438\u043a\u0441\u043d\u044b\u0435 \u0434\u0435\u0440\u0435\u0432\u044c\u044f \u0438 \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u044b\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u044b. \u041d\u043e \u044d\u0442\u043e \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u0430\u0439\u0441\u0431\u0435\u0440\u0433\u0430, \u0432 \u0433\u043b\u0443\u0431\u0438\u043d\u0435 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043a\u0440\u043e\u044e\u0442\u0441\u044f \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u044b\u0435 \u0432\u0435\u0439\u0432\u043b\u0435\u0442-\u0434\u0435\u0440\u0435\u0432\u044c\u044f, FM-\u0438\u043d\u0434\u0435\u043a\u0441\u044b, RMQ (range minimum queries), LCP (longest common prefix), \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u044b\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u044b \u0438 \u043e\u0433\u0440\u043e\u043c\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0434\u0440\u0443\u0433\u0438\u0445 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440, \u043f\u0440\u0438\u0433\u043e\u0434\u043d\u044b\u0445 \u043a succinct&#8217;\u0438\u0437\u0430\u0446\u0438\u0438. \u0423 \u043a\u0430\u0436\u0434\u043e\u0439 \u0438\u0437 \u043d\u0438\u0445 \u0441\u0432\u043e\u044f \u0441\u0444\u0435\u0440\u0430 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0438 \u0441\u0432\u043e\u0438 \u0441\u043e\u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u044f \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438-\u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u043e\u0441\u0442\u0438.<\/p>\n<p>  <\/p>\n<h2 id=\"epilog\">\u042d\u043f\u0438\u043b\u043e\u0433<\/h2>\n<p>  <\/p>\n<p>\u041a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u044b\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u0437\u0434\u043e\u0440\u043e\u0432\u043e \u043e\u0431\u043b\u0435\u0433\u0447\u0430\u044e\u0442 \u0436\u0438\u0437\u043d\u044c \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a\u0430\u043c \u043f\u043e\u0438\u0441\u043a\u043e\u0432\u044b\u0445 \u0434\u0432\u0438\u0436\u043a\u043e\u0432, \u043c\u043e\u0431\u0438\u043b\u044c\u043d\u044b\u0445 \u043f\u0440\u0438\u043b\u043e\u0436\u0435\u043d\u0438\u0439, \u0432\u044b\u0441\u043e\u043a\u043e\u043d\u0430\u0433\u0440\u0443\u0436\u0435\u043d\u043d\u044b\u0445 \u0441\u0435\u0440\u0432\u0438\u0441\u043e\u0432. \u0418 \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e. \u0412 \u043f\u0440\u0438\u043d\u0446\u0438\u043f\u0435 \u0434\u043b\u044f \u043b\u044e\u0431\u043e\u0433\u043e \u043f\u0440\u043e\u0435\u043a\u0442\u0430, \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0449\u0435\u0433\u043e \u0441 \u0440\u0430\u0441\u0442\u0443\u0449\u0438\u043c\u0438 \u043e\u0431\u044a\u0435\u043c\u0430\u043c\u0438 \u0434\u0430\u043d\u043d\u044b\u0445, \u043c\u043e\u0436\u0435\u0442 \u043d\u0430\u0441\u0442\u0443\u043f\u0438\u0442\u044c \u0447\u0430\u0441 X, \u043a\u043e\u0433\u0434\u0430 \u0431\u0443\u0442\u044b\u043b\u043e\u0447\u043d\u044b\u043c \u0433\u043e\u0440\u043b\u044b\u0448\u043a\u043e\u043c \u0432\u043d\u0435\u0437\u0430\u043f\u043d\u043e \u0441\u0442\u0430\u043d\u0443\u0442 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u0432 \u0438\u0445 \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438.<\/p>\n<p>  <\/p>\n<p>\u041d\u043e succinct \u2014 \u043d\u0435 \u0431\u0435\u0437\u0432\u0440\u0435\u0434\u043d\u044b\u0439 \u043f\u043e\u0434\u043e\u0440\u043e\u0436\u043d\u0438\u043a \u043d\u0430 \u043a\u043e\u043b\u0435\u043d\u043a\u0443, \u043e\u0442 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u00ab\u0445\u0443\u0436\u0435-\u0442\u043e \u0443\u0436 \u0442\u043e\u0447\u043d\u043e \u043d\u0435 \u0431\u0443\u0434\u0435\u0442\u00bb. Succinct \u2014 \u044d\u0442\u043e \u0434\u0435\u043c\u043e\u043d \u0441\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e\u043c \u0438\u043c\u0435\u043d. \u041f\u0440\u0438\u0437\u0432\u0430\u0442\u044c \u0438 \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u0442\u044c \u0438\u043c \u043f\u043e\u0434\u0432\u043b\u0430\u0441\u0442\u043d\u043e \u043b\u0438\u0448\u044c \u0438\u0441\u043a\u0443\u0448\u0435\u043d\u043d\u043e\u043c\u0443 \u0434\u0435\u043c\u043e\u043d\u043e\u043b\u043e\u0433\u0443, \u0438\u043c\u0435\u044e\u0449\u0435\u043c\u0443 \u043a\u0440\u0438\u0441\u0442\u0430\u043b\u044c\u043d\u043e\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u043e \u0445\u0438\u0442\u0440\u043e\u0441\u0442\u044f\u0445, \u043e\u043f\u0430\u0441\u043d\u043e\u0441\u0442\u044f\u0445 \u0438 \u043c\u043e\u0433\u0443\u0449\u0435\u0441\u0442\u0432\u0435 succinct. \u0414\u043e\u0441\u0442\u043e\u0432\u0435\u0440\u043d\u043e \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u0447\u0442\u043e \u0442\u0430\u043a\u0438\u0435 \u0445\u0440\u0430\u0431\u0440\u0435\u0446\u044b \u0436\u0438\u0432\u0443\u0442 \u0441\u0440\u0435\u0434\u0438 \u043d\u0430\u0441. \u041e\u043d\u0438 \u043f\u0440\u0438\u043b\u043e\u0436\u0438\u043b\u0438 \u0440\u0443\u043a\u0443 \u043a \u0440\u0435\u0434\u0430\u043a\u0442\u043e\u0440\u0443 \u043c\u0435\u0442\u043e\u0434\u0430 \u0432\u0432\u043e\u0434\u0430 (IME) \u0432 <a href=\"https:\/\/www.aclweb.org\/anthology\/W11-3503.pdf\">Google,<\/a> \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u043e\u043c\u0443 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044e \u0414\u041d\u041a \u0432 <a href=\"https:\/\/pdfs.semanticscholar.org\/3039\/65210e08d794398ddc5ed60322a205758255.pdf\">\u0413\u043e\u043d\u043a\u043e\u043d\u0433\u0441\u043a\u043e\u043c \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0438\u0442\u0435\u0442\u0435.<\/a> \u0412 <a href=\"https:\/\/github.com\/mapsme\/omim\">MAPS.ME<\/a> \u043c\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c succinct-\u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u0434\u043b\u044f \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0438 \u0433\u0435\u043e\u0433\u0440\u0430\u0444\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0432\u044b\u0441\u043e\u0442.<\/p>\n<p>  <\/p>\n<p>\u041a\u0430\u043a \u0431\u044b \u0442\u043e \u043d\u0438 \u0431\u044b\u043b\u043e, \u0437\u043d\u0430\u043d\u0438\u0435 \u043e \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u044b\u0445 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f\u0445 \u0434\u043b\u044f \u0437\u043d\u0430\u043a\u043e\u043c\u044b\u0445 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u0434\u0430\u043d\u043d\u044b\u0445 \u043e\u0434\u043d\u0430\u0436\u0434\u044b \u043c\u043e\u0436\u0435\u0442 \u0441\u0442\u0430\u0442\u044c \u0441\u0443\u0434\u044c\u0431\u043e\u043d\u043e\u0441\u043d\u044b\u043c \u043f\u0440\u0438 \u043f\u0440\u0438\u043d\u044f\u0442\u0438\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u0439 \u043e\u0431 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u043f\u0440\u043e\u0435\u043a\u0442\u0430. \u0418\u0431\u043e \u043a\u0430\u043a \u0441\u043a\u0430\u0437\u0430\u043b \u0414\u043e\u043d\u0430\u043b\u044c\u0434 \u041a., \u0432 97 % \u0441\u043b\u0443\u0447\u0430\u0435\u0432 \u043b\u0443\u0447\u0448\u0435 \u0437\u0430\u0431\u044b\u0442\u044c \u043e \u043c\u0438\u043a\u0440\u043e-\u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f\u0445: \u043f\u0440\u0435\u0436\u0434\u0435\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u043a\u043e\u0440\u0435\u043d\u044c \u0432\u0441\u0435\u0445 \u0437\u043e\u043b. \u041e\u0434\u043d\u0430\u043a\u043e \u043c\u044b \u043d\u0435 \u0434\u043e\u043b\u0436\u043d\u044b \u0443\u043f\u0443\u0441\u043a\u0430\u0442\u044c \u043d\u0430\u0448\u0438 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0432 \u043e\u0441\u0442\u0430\u0432\u0448\u0438\u0445\u0441\u044f 3 %.<\/p>\n<p>  <\/p>\n<h2 id=\"chto-dalshe\">\u0427\u0442\u043e \u0434\u0430\u043b\u044c\u0448\u0435?<\/h2>\n<p>  <\/p>\n<p>\u0414\u043b\u044f \u0442\u0435\u0445, \u043a\u0442\u043e \u0436\u0430\u0436\u0434\u0435\u0442 \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u043f\u043e\u0434\u0440\u043e\u0431\u043d\u043e\u0441\u0442\u0435\u0439 \u0438\u0437 \u043c\u0438\u0440\u0430 succinct:<\/p>\n<p>  <\/p>\n<ul>\n<li><a href=\"http:\/\/bitmagic.io\/rank-select.html\">\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u0432 \u0443\u0441\u043a\u043e\u0440\u0435\u043d\u0438\u044f rank\/select \u0432 Bitmagic Library. <\/a><\/li>\n<li><a href=\"https:\/\/www.xuanruiqi.com\/assets\/succinct.pdf\">\u0414\u0438\u0441\u0441\u0435\u0440\u0442\u0430\u0446\u0438\u044f, \u043f\u043e\u0441\u0432\u044f\u0449\u0435\u043d\u043d\u0430\u044f succinct. \u041e\u0441\u043e\u0431\u043e\u0435 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435 \u0443\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u0434\u0435\u0440\u0435\u0432\u044c\u044f\u043c \u043f\u043e\u0438\u0441\u043a\u0430.<\/a> <\/li>\n<li><a href=\"https:\/\/courses.csail.mit.edu\/6.851\/spring12\/lectures\/\">\u041b\u0435\u043a\u0446\u0438\u0438 \u0423\u043d\u0438\u0432\u0435\u0440\u0441\u0438\u0442\u0435\u0442\u0430 \u0412\u0430\u0442\u0435\u0440\u043b\u043e\u043e, \u0434\u0432\u0435 \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0443\u0434\u0435\u043b\u0435\u043d\u044b succinct.<\/a><\/li>\n<li><a href=\"http:\/\/www.cs.cmu.edu\/~dga\/csa.pdf\">\u042d\u043b\u0435\u043c\u0435\u043d\u0442\u0430\u0440\u043d\u043e\u0435 \u0432\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u044b\u0435 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u044b\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u044b, \u0432\u0441\u0435\u0433\u043e \u043d\u0430 18 \u043b\u0438\u0441\u0442\u043e\u0432.<\/a><\/li>\n<li><a href=\"https:\/\/people.csail.mit.edu\/mip\/papers\/succinct\/succinct.pdf\">\u0418\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u0441\u043a\u0430\u044f \u0441\u0442\u0430\u0442\u044c\u044f \u043f\u0440\u043e \u0442\u043e, \u043a\u0430\u043a \u0435\u0449\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u0435\u0435 \u0443\u0436\u0438\u043c\u0430\u0442\u044c succinct.<\/a><\/li>\n<li><a href=\"https:\/\/alexbowe.com\/rrr\/\">RRR \u2014 \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u043e\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0431\u0438\u0442\u043e\u0432\u044b\u0445 \u0432\u0435\u043a\u0442\u043e\u0440\u043e\u0432.<\/a><\/li>\n<\/ul>\n<p>  <\/p>\n<p>\u0414\u043b\u044f \u0442\u0435\u0445, \u043a\u0442\u043e \u0436\u0435\u043b\u0430\u0435\u0442 \u043f\u043e\u0441\u043a\u043e\u0440\u0435\u0435 \u043f\u0435\u0440\u0435\u0439\u0442\u0438 \u043e\u0442 \u0442\u0435\u043e\u0440\u0438\u0438 \u043a \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435:<\/p>\n<p>  <\/p>\n<ul>\n<li><a href=\"https:\/\/github.com\/simongog\/sdsl-lite\">\u041f\u0440\u043e\u0435\u043a\u0442 Succinct Data Structures Library \u043d\u0430 C++.<\/a><\/li>\n<li><a href=\"https:\/\/github.com\/tlk00\/BitMagic\">\u041f\u0440\u043e\u0435\u043a\u0442 BitMagic \u043d\u0430 C++.<\/a><\/li>\n<li><a href=\"https:\/\/pypi.org\/project\/elias-fano\/\">\u041f\u0430\u043a\u0435\u0442 \u0441 succinct-\u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0435\u0439 Elias-Fano \u043d\u0430 Python.<\/a><\/li>\n<li><a href=\"https:\/\/docs.rs\/succinct\/0.5.2\/succinct\/#modules\">\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 succinct-\u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u043d\u0430 Rust.<\/a><\/li>\n<\/ul>\n<\/div>\n<p> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/company\/mailru\/blog\/479822\/\"> https:\/\/habr.com\/ru\/company\/mailru\/blog\/479822\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n<div class=\"post__text post__text-html\" id=\"post-content-body\" data-io-article-url=\"https:\/\/habr.com\/ru\/company\/mailru\/blog\/479822\/\">\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/uv\/si\/qc\/uvsiqcnik2vqvi6zzwvjifbrv2w.jpeg\" alt=\"image\"><\/p>\n<p>  <\/p>\n<p>\u041a\u0430\u043a \u0431\u044b\u0442\u044c, \u0435\u0441\u043b\u0438 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0438\u0441\u043a\u0430 \u0440\u0430\u0437\u0440\u043e\u0441\u043b\u043e\u0441\u044c \u043d\u0430 \u0432\u0441\u044e \u043e\u043f\u0435\u0440\u0430\u0442\u0438\u0432\u043a\u0443 \u0438 \u0432\u043e\u0442-\u0432\u043e\u0442 \u043f\u043e\u0434\u043e\u043f\u0440\u0435\u0442 \u043a\u043e\u0440\u043d\u044f\u043c\u0438 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0435 \u0441\u0442\u043e\u0439\u043a\u0438 \u0432 \u0441\u0435\u0440\u0432\u0435\u0440\u043d\u043e\u0439? \u0427\u0442\u043e \u0434\u0435\u043b\u0430\u0442\u044c \u0441 \u0438\u043d\u0432\u0435\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u043c \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u043c, \u0436\u0430\u0434\u043d\u044b\u043c \u0434\u043e \u0440\u0435\u0441\u0443\u0440\u0441\u043e\u0432?\u00a0\u0417\u0430\u0432\u044f\u0437\u044b\u0432\u0430\u0442\u044c \u043b\u0438 \u0441 \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u043a\u043e\u0439 \u043f\u043e\u0434 Android, \u0435\u0441\u043b\u0438 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044e \u043f\u0440\u0438\u043b\u0435\u0442\u0430\u0435\u0442 \u00ab\u041f\u0430\u043c\u044f\u0442\u044c \u0442\u0435\u043b\u0435\u0444\u043e\u043d\u0430 \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u0430\u00bb, \u0430 \u043f\u0440\u0438\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u0435\u0434\u0432\u0430 \u043d\u0430 \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0435 \u0437\u0430\u0433\u0440\u0443\u0437\u043a\u0438 \u0432\u0430\u0436\u043d\u043e\u0433\u043e \u043a\u043e\u043d\u0442\u0435\u0439\u043d\u0435\u0440\u0430?<\/p>\n<p>  <\/p>\n<p>\u0412 \u0446\u0435\u043b\u043e\u043c, \u043c\u043e\u0436\u043d\u043e \u043b\u0438 \u0441\u0436\u0430\u0442\u044c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0434\u0430\u043d\u043d\u044b\u0445, \u0447\u0442\u043e\u0431\u044b \u043e\u043d\u0430 \u0437\u0430\u043d\u0438\u043c\u0430\u043b\u0430 \u0437\u0430\u043c\u0435\u0442\u043d\u043e \u043c\u0435\u043d\u044c\u0448\u0435 \u043c\u0435\u0441\u0442\u0430, \u043d\u043e \u043d\u0435 \u0442\u0435\u0440\u044f\u043b\u0430 \u043f\u0440\u0438\u0441\u0443\u0449\u0438\u0445 \u0435\u0439 \u0434\u043e\u0441\u0442\u043e\u0438\u043d\u0441\u0442\u0432? \u0427\u0442\u043e\u0431\u044b \u0434\u043e\u0441\u0442\u0443\u043f \u043a \u0445\u044d\u0448-\u0442\u0430\u0431\u043b\u0438\u0446\u0435 \u043e\u0441\u0442\u0430\u0432\u0430\u043b\u0441\u044f \u0431\u044b\u0441\u0442\u0440\u044b\u043c, \u0430 \u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u043b\u043e \u0441\u0432\u043e\u0438 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430. \u0414\u0430, \u043c\u043e\u0436\u043d\u043e! \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0438 \u043f\u043e\u044f\u0432\u0438\u043b\u043e\u0441\u044c \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0442\u0438\u043a\u0438 \u00abSuccinct data structures\u00bb, \u0438\u0441\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435 \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u043e\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u0434\u0430\u043d\u043d\u044b\u0445. \u041e\u043d\u043e \u0440\u0430\u0437\u0432\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0441 \u043a\u043e\u043d\u0446\u0430 80-\u0445 \u0433\u043e\u0434\u043e\u0432 \u0438 \u043f\u0440\u044f\u043c\u043e \u0441\u0435\u0439\u0447\u0430\u0441 \u043f\u0435\u0440\u0435\u0436\u0438\u0432\u0430\u0435\u0442 \u0440\u0430\u0441\u0446\u0432\u0435\u0442 \u0432 \u043b\u0443\u0447\u0430\u0445 \u0441\u043b\u0430\u0432\u044b big data \u0438 highload.<\/p>\n<p>  <\/p>\n<p>\u0410 \u0442\u0435\u043c \u0432\u0440\u0435\u043c\u0435\u043d\u0435\u043c \u043d\u0430 \u0425\u0430\u0431\u0440\u0435 \u043d\u0430\u0439\u0434\u0435\u0442\u0441\u044f \u043b\u0438 \u0433\u0435\u0440\u043e\u0439, \u0441\u043f\u043e\u0441\u043e\u0431\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0441\u043a\u043e\u0432\u043e\u0433\u043e\u0432\u043e\u0440\u0438\u0442\u044c \u0442\u0440\u0438 \u0440\u0430\u0437\u0430 \u043f\u043e\u0434\u0440\u044f\u0434<br \/>  [s\u0259k\u02c8s\u026a\u014bkt]?<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-297503","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/297503","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=297503"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/297503\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=297503"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=297503"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=297503"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}