Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"VastUniverse","updateTime":1706535262000,"title":"C++ segment tree class","dislikeCnt":0,"content":"```cpp\ntemplate\u003ctypename T\u003e class segment_tree // [1, n]\n{\n private:\n vector\u003cT\u003e s, t;\n int length;\n\n int ls(int x)\n {\n return x \u003c\u003c 1;\n }\n\n int rs(int x)\n {\n return x \u003c\u003c 1 | 1;\n }\n\n int mid(int l, int r)\n {\n return (l + r) \u003e\u003e 1;\n }\n\n void push_up(int p)\n {\n s[p] \u003d s[ls(p)] + s[rs(p)];\n }\n\n void add_lazy_tag(int p, int l, int r, int x)\n {\n s[p] +\u003d (r - l + 1) * x;\n t[p] +\u003d x;\n }\n\n void push_down(int p, int l, int r)\n {\n if (!t[p])\n return;\n add_lazy_tag(ls(p), l, mid(l, r), t[p]);\n add_lazy_tag(rs(p), mid(l, r) + 1, r, t[p]);\n t[p] \u003d 0;\n }\n\n void __rebuild(T* iter, int l, int r, int p \u003d 1)\n {\n t[p] \u003d 0;\n if (l \u003d\u003d r)\n {\n s[p] \u003d iter[l];\n return;\n }\n __rebuild(iter, l, mid(l, r), ls(p));\n __rebuild(iter, mid(l, r) + 1, r, rs(p));\n push_up(p);\n }\n public:\n segment_tree(){}\n\n segment_tree(T* iter, int l, int r)\n {\n rebuild(iter, l, r);\n }\n\n void rebuild(T* iter, int l, int r)\n {\n length \u003d r;\n t \u003d s \u003d vector\u003cT\u003e((r + 1) * 4 + 10, 0);\n __rebuild(iter, l, r);\n }\n\n void add_range(int L, int R, T x, int p \u003d 1, int l \u003d 1, int r \u003d -1)\n {\n if (r \u003d\u003d -1)\n {\n r \u003d length;\n }\n if (r \u003c L || R \u003c l)\n return;\n if (L \u003c\u003d l \u0026\u0026 r \u003c\u003d R)\n return add_lazy_tag(p, l, r, x);\n push_down(p, l, r);\n add_range(L, R, x, ls(p), l, mid(l, r));\n add_range(L, R, x, rs(p), mid(l, r) + 1, r);\n push_up(p);\n }\n\n void add_one(int P, T x)\n {\n add_range(P, P, x);\n }\n\n T query(int L, int R, int p \u003d 1, int l \u003d 1, int r \u003d -1)\n {\n if (r \u003d\u003d -1)\n {\n r \u003d length;\n }\n if (r \u003c L || R \u003c l)\n return 0;\n if (L \u003c\u003d l \u0026\u0026 r \u003c\u003d R)\n return s[p];\n push_down(p, l, r);\n return query(L, R, ls(p), l, mid(l, r)) + query(L, R, rs(p), mid(l, r) + 1, r);\n }\n\n int size()\n {\n return length;\n }\n};\n```\n###### Note: The index starts from 1, and the add function parameter is an open interval","threadId":180980,"likeCnt":1,"createTime":1706531541000,"isWorkbook":false,"viewCnt":52,"openness":2,"fav":false,"id":4527,"trustable":false}