Artifact 5a7c5bc1ec0fdf3078ab4ba75a3c529f9dbc0d2d:
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 2d 2d 2d 2d Div1 LV3.//----
00a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00b0: 2d 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 0a 0a 74 65 6d 70 6c ---------..templ
00e0: 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 54 20 3d ate<typename T =
00f0: 20 4c 4c 3e 0a 73 74 72 75 63 74 20 46 65 6e 77 LL>.struct Fenw
0100: 69 63 6b 54 72 65 65 0a 7b 0a 09 76 65 63 74 6f ickTree.{..vecto
0110: 72 3c 54 3e 20 78 3b 0a 09 46 65 6e 77 69 63 6b r<T> x;..Fenwick
0120: 54 72 65 65 28 73 69 7a 65 5f 74 20 6e 2c 20 63 Tree(size_t n, c
0130: 6f 6e 73 74 20 54 26 20 76 20 3d 20 54 28 29 29 onst T& v = T())
0140: 20 3a 20 78 28 6e 2c 20 76 29 20 7b 7d 0a 0a 09 : x(n, v) {}...
0150: 76 6f 69 64 20 69 6e 63 72 28 20 69 6e 74 20 6b void incr( int k
0160: 2c 20 63 6f 6e 73 74 20 54 26 20 61 20 29 20 7b , const T& a ) {
0170: 20 2f 2f 20 7a 5b 6b 5d 20 2b 3d 20 61 3b 0a 09 // z[k] += a;..
0180: 09 66 6f 72 28 3b 20 6b 20 3c 20 78 2e 73 69 7a .for(; k < x.siz
0190: 65 28 29 3b 20 6b 7c 3d 6b 2b 31 29 0a 09 09 09 e(); k|=k+1)....
01a0: 78 5b 6b 5d 20 2b 3d 20 61 3b 0a 09 7d 0a 0a 09 x[k] += a;..}...
01b0: 54 20 73 75 6d 28 69 6e 74 20 69 2c 20 69 6e 74 T sum(int i, int
01c0: 20 6a 29 20 7b 20 2f 2f 20 7a 5b 69 5d 2b 2e 2e j) { // z[i]+..
01d0: 2e 2b 7a 5b 6a 5d 20 3a 20 69 6e 63 6c 75 73 69 .+z[j] : inclusi
01e0: 76 65 0a 09 09 69 66 28 69 29 0a 09 09 09 72 65 ve...if(i)....re
01f0: 74 75 72 6e 20 73 75 6d 28 30 2c 20 6a 29 20 2d turn sum(0, j) -
0200: 20 73 75 6d 28 30 2c 20 69 2d 31 29 3b 0a 09 09 sum(0, i-1);...
0210: 65 6c 73 65 20 7b 0a 09 09 09 54 20 76 20 3d 20 else {....T v =
0220: 54 28 29 3b 0a 09 09 09 66 6f 72 28 3b 20 6a 3e T();....for(; j>
0230: 3d 30 3b 20 6a 3d 28 6a 26 28 6a 2b 31 29 29 2d =0; j=(j&(j+1))-
0240: 31 29 0a 09 09 09 09 76 20 2b 3d 20 78 5b 6a 5d 1).....v += x[j]
0250: 3b 0a 09 09 09 72 65 74 75 72 6e 20 76 3b 0a 09 ;....return v;..
0260: 09 7d 0a 09 7d 0a 7d 3b 0a .}..}.};.