Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"VastUniverse","updateTime":1706535501000,"title":"C++ BIT class","dislikeCnt":0,"content":"```cpp\ntemplate\u003ctypename T\u003e class BIT // [1, n]\n{\n vector\u003cint\u003e tree;\n int length;\n\n int lowbit(int n)\n {\n return n \u0026 (-n);\n }\n public:\n BIT(){}\n\n BIT(T* iter, int l, int r)\n {\n length \u003d r;\n tree \u003d vector\u003cT\u003e(r + 5);\n for (int i \u003d l; i \u003c\u003d r; i++)\n {\n add(i, iter[i]);\n }\n }\n\n T query(int i)\n {\n T ans \u003d 0;\n for (int j \u003d i; j \u003e 0; j -\u003d lowbit(j))\n {\n ans +\u003d tree[j];\n }\n return ans;\n }\n\n T query(int i, int j) // [i, j]\n {\n return query(j) - query(i - 1);\n }\n\n void add(int i, T x)\n {\n for (int j \u003d i; j \u003c tree.size(); j +\u003d lowbit(j))\n {\n tree[j] +\u003d x;\n }\n }\n};\n```\n\n###### Note: The index starts from 1, and the query function parameter is an open interval","threadId":180983,"likeCnt":1,"createTime":1706535501000,"isWorkbook":false,"viewCnt":63,"openness":2,"fav":false,"id":4528,"trustable":false}