0-indexed
| 24 | } |
| 25 | //0-indexed |
| 26 | struct SqrtTree { |
| 27 | int n, llg, indexSz; |
| 28 | vector<SqrtTreeItem> v; |
| 29 | vector<int> clz, layers, onLayer; |
| 30 | vector< vector<SqrtTreeItem> > pref, suf, between; |
| 31 | |
| 32 | inline void buildBlock(int layer, int l, int r) { |
| 33 | pref[layer][l] = v[l]; |
| 34 | for (int i = l + 1; i < r; i++) { |
| 35 | pref[layer][i] = op(pref[layer][i - 1], v[i]); |
| 36 | } |
| 37 | suf[layer][r - 1] = v[r - 1]; |
| 38 | for (int i = r - 2; i >= l; i--) { |
| 39 | suf[layer][i] = op(v[i], suf[layer][i + 1]); |
| 40 | } |
| 41 | } |
| 42 | |
| 43 | inline void buildBetween(int layer, int lBound, int rBound, int betweenOffs) { |
| 44 | int bSzLog = (layers[layer] + 1) >> 1; |
| 45 | int bCntLog = layers[layer] >> 1; |
| 46 | int bSz = 1 << bSzLog; |
| 47 | int bCnt = (rBound - lBound + bSz - 1) >> bSzLog; |
| 48 | for (int i = 0; i < bCnt; i++) { |
| 49 | SqrtTreeItem ans; |
| 50 | for (int j = i; j < bCnt; j++) { |
| 51 | SqrtTreeItem add = suf[layer][lBound + (j << bSzLog)]; |
| 52 | ans = (i == j) ? add : op(ans, add); |
| 53 | between[layer - 1][betweenOffs + lBound + (i << bCntLog) + j] = ans; |
| 54 | } |
| 55 | } |
| 56 | } |
| 57 | |
| 58 | inline void buildBetweenZero() { |
| 59 | int bSzLog = (llg + 1) >> 1; |
| 60 | for (int i = 0; i < indexSz; i++) { |
| 61 | v[n + i] = suf[0][i << bSzLog]; |
| 62 | } |
| 63 | build(1, n, n + indexSz, (1 << llg) - n); |
| 64 | } |
| 65 | |
| 66 | inline void updateBetweenZero(int bid) { |
| 67 | int bSzLog = (llg + 1) >> 1; |
| 68 | v[n + bid] = suf[0][bid << bSzLog]; |
| 69 | update(1, n, n + indexSz, (1 << llg) - n, n + bid); |
| 70 | } |
| 71 | |
| 72 | void build(int layer, int lBound, int rBound, int betweenOffs) { |
| 73 | if (layer >= (int)layers.size()) { |
| 74 | return; |
| 75 | } |
| 76 | int bSz = 1 << ((layers[layer] + 1) >> 1); |
| 77 | for (int l = lBound; l < rBound; l += bSz) { |
| 78 | int r = min(l + bSz, rBound); |
| 79 | buildBlock(layer, l, r); |
| 80 | build(layer + 1, l, r, betweenOffs); |
| 81 | } |
| 82 | if (layer == 0) { |
| 83 | buildBetweenZero(); |