POJ 3468 解题报告

这是按照https://blog.csdn.net/thestoryofsnow/article/details/40942009刷的第4道题，感觉难度已经上来了。看到题目就知道可以用segment tree,于是按照geeksforgeeks的方法做了实现：https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/。然后就是一系列的WA, RE和TLE。主要原因是不熟悉64位int的表示方法。POJ不认识stdint.h，按照报错google了下似乎是windows服务器。RE是之前没有理解对segment tree的最大index的范围。实际上，对于有n个leaf（实际需要保存的数），那么中间节点为n-1个，所以总结点是2n-1个。但是由于segment tree是full binary tree但不是complete binary tree，所以array中有些段是空的，index的最大范围是2 * (N + (N - 1) - 1) + 2 + 1 = 4 * N - 1(这个数应该是取不到的)。所以我最后开了4N的空间。这是按照https://blog.csdn.net/thestoryofsnow/articl