{"id":1530,"date":"2020-12-25T22:24:29","date_gmt":"2020-12-26T06:24:29","guid":{"rendered":"http:\/\/209.126.2.187\/?p=1530"},"modified":"2021-01-12T21:07:12","modified_gmt":"2021-01-13T05:07:12","slug":"segment-tree-template","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2020\/12\/25\/segment-tree-template\/","title":{"rendered":"Segment Tree Template"},"content":{"rendered":"\n<h3 class=\"wp-block-heading\">Range Update<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp line-numbers\">constexpr int kMaxN = 100'001;\nusing ll = long long;\nstruct Info {\n  int max;\n};\ntemplate &lt;typename InfoT&gt;\nclass SegmentTree {\n private:\n  int n_;\n  \/\/ val\n  static int tree_nums_[kMaxN];\n  \/\/ processed info for current tree\n  static InfoT info_[kMaxN * 4];\n  \/\/ unprocessed info for subtrees\n  static ll tag_[kMaxN * 4];\n  \/\/ l, r, tree_nums =&gt; info_root\n  inline InfoT Init(int l, int r, int num) { return InfoT{0}; }\n  \/\/ l, r, info_l, info_r =&gt; info_root\n  inline InfoT Merge(int l, int r, InfoT info_l, InfoT info_r) {\n    if (info_l.max &gt; info_r.max) {\n      return info_l;\n    }\n    return info_r;\n  }\n  \/\/ l, r, origin_info, val =&gt; new_info\n  inline InfoT Update(int l, int r, InfoT origin, int val) {\n    origin.max += val;\n    return origin;\n  }\n  \/\/ l, r, origin_info, val =&gt; new_info\n  inline InfoT Set(int l, int r, InfoT origin, int val) {\n    origin.max = val;\n    return origin;\n  }\n  inline InfoT QueryReturnDefault() { return InfoT{INT_MIN}; }\n  void Build(int root, int l, int r) {\n    if (l &gt; r) {\n      return;\n    }\n    if (l == r) {\n      info_[root] = Init(l, r, tree_nums_[l]);\n      return;\n    }\n    int mid = l + (r - l) \/ 2;\n    Build(root * 2, l, mid);\n    Build(root * 2 + 1, mid + 1, r);\n    info_[root] = Merge(l, r, info_[root * 2], info_[root * 2 + 1]);\n  }\n  \/\/ Push down current tag before updating subtree\n  void PushDownRangeAdd(int root, int l, int r) {\n    int mid = l + (r - l) \/ 2;\n    int val = tag_[root];\n    info_[root * 2] = Update(l, mid, info_[root * 2], val);\n    tag_[root * 2] += val;\n    info_[root * 2 + 1] = Update(l, mid, info_[root * 2 + 1], val);\n    tag_[root * 2 + 1] += val;\n    tag_[root] = 0;\n  }\n  \/\/ Push down current tag before updating subtree\n  void PushDown(int root, int l, int r) {\n    int mid = l + (r - l) \/ 2;\n    int val = tag_[root];\n    info_[root * 2] = Update(l, mid, info_[root * 2], val);\n    tag_[root * 2] += val;\n    info_[root * 2 + 1] = Update(l, mid, info_[root * 2 + 1], val);\n    tag_[root * 2 + 1] += val;\n    tag_[root] = 0;\n  }\n  \/\/ Range + \/ -\n  void Update(int root, int l, int r, int q_l, int q_r, int val) {\n    if (q_l &lt;= l &amp;&amp; r &lt;= q_r) {\n      info_[root] = Update(l, r, info_[root], val);\n      tag_[root] += val;\n      return;\n    }\n    if (q_l &gt; r || q_r &lt; l) {\n      return;\n    }\n    int mid = l + (r - l) \/ 2;\n    PushDownRangeAdd(root, l, r);\n    Update(root * 2, l, mid, q_l, q_r, val);\n    Update(root * 2 + 1, mid + 1, r, q_l, q_r, val);\n    info_[root] = Merge(l, r, info_[root * 2], info_[root * 2 + 1]);\n  }  \/\/ Single point set\n  void Set(int root, int l, int r, int q_index, int val) {\n    if (q_index == l &amp;&amp; r == q_index) {\n      info_[root] = Set(l, r, info_[root], val);\n      return;\n    }\n    if (q_index &gt; r || q_index &lt; l) {\n      return;\n    }\n    int mid = l + (r - l) \/ 2;\n    PushDownRangeAdd(root, l, r);\n    Set(root * 2, l, mid, q_index, val);\n    Set(root * 2 + 1, mid + 1, r, q_index, val);\n    info_[root] = Merge(l, r, info_[root * 2], info_[root * 2 + 1]);\n  }\n  InfoT Query(int root, int l, int r, int q_l, int q_r) {\n    if (q_l &lt;= l &amp;&amp; r &lt;= q_r) {\n      return info_[root];\n    }\n    if (q_l &gt; r || q_r &lt; l) {\n      return QueryReturnDefault();\n    }\n    int mid = l + (r - l) \/ 2;\n    PushDownRangeAdd(root, l, r);\n    return Merge(l, r, Query(root * 2, l, mid, q_l, q_r),\n                 Query(root * 2 + 1, mid + 1, r, q_l, q_r));\n  }\n\n public:\n  explicit SegmentTree(vector&lt;int&gt; const&amp; nums) : n_(nums.size()) {\n    memcpy(tree_nums_, nums.data(), sizeof(int) * nums.size());\n    fill(info_, info_ + sizeof(info_) \/ sizeof(InfoT), InfoT());\n    memset(tag_, 0, sizeof(tag_));\n    Build(1, 0, n_ - 1);\n  }\n  explicit SegmentTree(int n) : n_(n) {\n    memset(tree_nums_, 0, sizeof(int) * n);\n    fill(info_, info_ + sizeof(info_) \/ sizeof(InfoT), InfoT());\n    memset(tag_, 0, sizeof(tag_));\n    Build(1, 0, n_ - 1);\n  }\n  void Update(int q_l, int q_r, int val) {\n    if (q_l &gt; q_r) {\n      return;\n    }\n    Update(1, 0, n_ - 1, q_l, q_r, val);\n  }\n  void Set(int q_index, int val) { Set(1, 0, n_ - 1, q_index, val); }\n  InfoT Query(int q_l, int q_r) {\n    if (q_l &gt; q_r) {\n      return QueryReturnDefault();\n    }\n    return Query(1, 0, n_ - 1, q_l, q_r);\n  }\n};\ntemplate &lt;typename InfoT&gt;\nint SegmentTree&lt;InfoT&gt;::tree_nums_[kMaxN];\ntemplate &lt;typename InfoT&gt;\nInfoT SegmentTree&lt;InfoT&gt;::info_[kMaxN * 4];\ntemplate &lt;typename InfoT&gt;\nll SegmentTree&lt;InfoT&gt;::tag_[kMaxN * 4];<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">Index Update<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp line-numbers\"><pre class=\"wp-block-code\"><code class=\"\">\nconstexpr int kMaxN = 100'005;\nusing ll = long long;\n\ntemplate &lt;typename InfoT&gt;\nclass SegmentTree {\n public:\n  SegmentTree(int n) : n_(n) {\n    memset(tree_nums_, 0, sizeof(tree_nums_));\n    fill(info_, info_ + sizeof(info_) \/ sizeof(InfoT), InfoT());\n    Build(1, 0, n_ - 1);\n  }\n  SegmentTree(vector&lt;int&gt;<int> const&amp; nums) : n_(nums.size()) {\n    memcpy(tree_nums_, nums.data(), sizeof(int) * nums.size());\n    fill(info_, info_ + sizeof(info_) \/ sizeof(InfoT), InfoT());\n    Build(1, 0, n_ - 1);\n  }\n\n  void Update(int q_index, int val) { Update(1, 0, n_ - 1, q_index, val); }\n  int Query(int q_l, int q_r) { return Query(1, 0, n_ - 1, q_l, q_r); }\n  void Set(int q_index, int val) { Set(1, 0, n_ - 1, q_index, val); }\n\n private:\n  int n_;\n  \/\/ val\n  static int tree_nums_[kMaxN];\n  \/\/ processed info for current tree\n  static InfoT info_[kMaxN * 4];\n\n  \/\/ l, r, tree_nums =&gt; info_root\n  inline InfoT Init(int l, int r, int num) { return InfoT{num}; }\n  \/\/ l, r, info_l, info_r =&gt; info_root\n  inline InfoT Merge(int l, int r, InfoT info_l, InfoT info_r) {\n    return info_l + info_r;\n  }\n  \/\/ l, r, origin_info, val =&gt; new_info\n  inline InfoT Update(int l, int r, InfoT origin, int val) {\n    return origin + val;\n  }\n  \/\/ l, r, origin_info, val =&gt; new_info\n  inline InfoT Set(int l, int r, InfoT origin, int val) { return val; }\n  inline InfoT QueryReturnDefault() { return InfoT{0}; }\n\n  void Build(int root, int l, int r) {\n    if (l &gt; r) {\n      return;\n    }\n    if (l == r) {\n      info_[root] = Init(l, r, tree_nums_[l]);\n      return;\n    }\n    int mid = l + (r - l) \/ 2;\n    Build(root * 2, l, mid);\n    Build(root * 2 + 1, mid + 1, r);\n    info_[root] = Merge(l, r, info_[root * 2], info_[root * 2 + 1]);\n  }\n\n  void Update(int root, int l, int r, int q_index, int val) {\n    if (l &gt; q_index || r &lt; q_index) {\n      return;\n    }\n    if (l == r) {\n      info_[root] = Update(l, r, info_[root], val);\n      return;\n    }\n    int mid = l + (r - l) \/ 2;\n    Update(root * 2, l, mid, q_index, val);\n    Update(root * 2 + 1, mid + 1, r, q_index, val);\n    info_[root] = Merge(l, r, info_[root * 2], info_[root * 2 + 1]);\n  }\n\n  void Set(int root, int l, int r, int q_index, int val) {\n    if (l &gt; q_index || r &lt; q_index) {\n      return;\n    }\n    if (l == r) {\n      info_[root] = Set(l, r, info_[root], val);\n      return;\n    }\n    int mid = l + (r - l) \/ 2;\n    Set(root * 2, l, mid, q_index, val);\n    Set(root * 2 + 1, mid + 1, r, q_index, val);\n    info_[root] = Merge(l, r, info_[root * 2], info_[root * 2 + 1]);\n  }\n\n  int Query(int root, int l, int r, int q_l, int q_r) {\n    if (q_l &gt; r || q_r &lt; l) {\n      return QueryReturnDefault();\n    }\n    if (q_l &lt;= l &amp;&amp; r &lt;= q_r) {\n      return info_[root];\n    }\n    int mid = l + (r - l) \/ 2;\n    return Merge(l, r, Query(root * 2, l, mid, q_l, q_r),\n                 Query(root * 2 + 1, mid + 1, r, q_l, q_r));\n  }\n};\n\ntemplate &lt;typename InfoT&gt;\nInfoT SegmentTree<infot>::info_[kMaxN * 4];\n\ntemplate &lt;typename InfoT&gt;\nint SegmentTree<infot>::tree_nums_[kMaxN];\n<\/infot><\/infot><\/int><\/code><\/pre><\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Range Update Index Update<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,67,51],"tags":[],"class_list":["post-1530","post","type-post","status-publish","format-standard","hentry","category-alg","category-algorithm-template","category-segment-tree"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1530","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/comments?post=1530"}],"version-history":[{"count":13,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1530\/revisions"}],"predecessor-version":[{"id":1555,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1530\/revisions\/1555"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1530"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1530"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1530"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}