| 105 | } |
| 106 | |
| 107 | inline SqrtTreeItem query(int l, int r, int betweenOffs, int base) { |
| 108 | if (l == r) { |
| 109 | return v[l]; |
| 110 | } |
| 111 | if (l + 1 == r) { |
| 112 | return op(v[l], v[r]); |
| 113 | } |
| 114 | int layer = onLayer[clz[(l - base) ^ (r - base)]]; |
| 115 | int bSzLog = (layers[layer] + 1) >> 1; |
| 116 | int bCntLog = layers[layer] >> 1; |
| 117 | int lBound = (((l - base) >> layers[layer]) << layers[layer]) + base; |
| 118 | int lBlock = ((l - lBound) >> bSzLog) + 1; |
| 119 | int rBlock = ((r - lBound) >> bSzLog) - 1; |
| 120 | SqrtTreeItem ans = suf[layer][l]; |
| 121 | if (lBlock <= rBlock) { |
| 122 | SqrtTreeItem add = (layer == 0) ? ( |
| 123 | query(n + lBlock, n + rBlock, (1 << llg) - n, n) |
| 124 | ) : ( |
| 125 | between[layer - 1][betweenOffs + lBound + (lBlock << bCntLog) + rBlock] |
| 126 | ); |
| 127 | ans = op(ans, add); |
| 128 | } |
| 129 | ans = op(ans, pref[layer][r]); |
| 130 | return ans; |
| 131 | } |
| 132 | |
| 133 | inline SqrtTreeItem query(int l, int r) { |
| 134 | return query(l, r, 0, 0); |