Artifact 0057b5a349c301818429793e89ebe0fd539d7f0e:
0000: 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d //--------------
0010: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a ---------------.
0040: 2f 2f 20 46 65 6e 77 69 63 6b 20 54 72 65 65 0a // Fenwick Tree.
0050: 2f 2f 20 20 20 4f 28 6c 6f 67 20 4e 29 20 70 65 // O(log N) pe
0060: 72 20 65 61 63 68 20 6f 70 65 72 61 74 69 6f 6e r each operation
0070: 0a 2f 2f 0a 2f 2f 20 56 65 72 69 66 69 65 64 20 .//.// Verified
0080: 62 79 0a 2f 2f 20 20 20 2d 20 53 52 4d 34 32 34 by.// - SRM424
0090: 20 44 69 76 31 20 4c 56 33 0a 2f 2f 20 20 20 2d Div1 LV3.// -
00a0: 20 54 43 4f 31 32 20 52 32 43 20 4c 56 32 0a 2f TCO12 R2C LV2./
00b0: 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d /---------------
00c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 0a --------------..
00f0: 74 65 6d 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d template<typenam
0100: 65 20 54 3d 4c 4c 3e 0a 73 74 72 75 63 74 20 46 e T=LL>.struct F
0110: 65 6e 77 69 63 6b 54 72 65 65 0a 7b 0a 09 76 65 enwickTree.{..ve
0120: 63 74 6f 72 3c 54 3e 20 78 3b 0a 09 46 65 6e 77 ctor<T> x;..Fenw
0130: 69 63 6b 54 72 65 65 28 73 69 7a 65 5f 74 20 6e ickTree(size_t n
0140: 29 20 3a 20 78 28 6e 29 20 7b 7d 0a 0a 09 76 6f ) : x(n) {}...vo
0150: 69 64 20 69 6e 63 72 28 20 69 6e 74 20 6b 2c 20 id incr( int k,
0160: 63 6f 6e 73 74 20 54 26 20 61 20 29 20 7b 20 2f const T& a ) { /
0170: 2f 20 7a 5b 6b 5d 20 2b 3d 20 61 3b 0a 09 09 66 / z[k] += a;...f
0180: 6f 72 28 3b 20 6b 20 3c 20 78 2e 73 69 7a 65 28 or(; k < x.size(
0190: 29 3b 20 6b 7c 3d 6b 2b 31 29 0a 09 09 09 78 5b ); k|=k+1)....x[
01a0: 6b 5d 20 2b 3d 20 61 3b 0a 09 7d 0a 09 54 20 73 k] += a;..}..T s
01b0: 75 6d 28 69 6e 74 20 69 2c 20 69 6e 74 20 6a 29 um(int i, int j)
01c0: 20 7b 20 2f 2f 20 53 69 67 6d 61 20 7a 5b 69 2c { // Sigma z[i,
01d0: 6a 29 20 65 78 63 6c 2e 0a 09 09 72 65 74 75 72 j) excl....retur
01e0: 6e 20 73 75 6d 5f 69 6d 70 6c 28 6a 2d 31 29 20 n sum_impl(j-1)
01f0: 2d 20 73 75 6d 5f 69 6d 70 6c 28 69 2d 31 29 3b - sum_impl(i-1);
0200: 0a 09 7d 0a 09 54 20 73 75 6d 5f 69 6d 70 6c 28 ..}..T sum_impl(
0210: 69 6e 74 20 6a 29 20 7b 20 2f 2f 20 53 69 67 6d int j) { // Sigm
0220: 61 20 7a 5b 30 2c 6a 5d 20 69 6e 63 6c 2e 0a 09 a z[0,j] incl...
0230: 09 54 20 76 20 3d 20 54 28 29 3b 0a 09 09 66 6f .T v = T();...fo
0240: 72 28 3b 20 6a 3e 3d 30 3b 20 6a 3d 28 6a 26 28 r(; j>=0; j=(j&(
0250: 6a 2b 31 29 29 2d 31 29 0a 09 09 09 76 20 2b 3d j+1))-1)....v +=
0260: 20 78 5b 6a 5d 3b 0a 09 09 72 65 74 75 72 6e 20 x[j];...return
0270: 76 3b 0a 09 7d 0a 7d 3b 0a v;..}.};.