POJ2352 假设数组a[1..n]，那么查询a[1]+...+a[n]的时间是log级别的，而且是一个在线的数据结构，支持随时修改某个元素的值，复杂度也为log级别。 来观察这个图： 令这棵树的结点编号为C1，C2...Cn。令每个结点的值为这棵树的值的总和，那么容易发现： C1 = A1 C2 = A1 + A2 C3 = A3 C4 = A1 + A2 + A3 + A4 C5 =

目录 今天知识点 求交点转化求逆序对，每次操作都维护一个y点的前缀和 树的变动转化成一维数组的变动，利用时间戳将节点转化成区间 离散化数组来求逆序对数 先将y排序，然后每加入一个就点更新求一次前缀和 POJ3067：日本         思路： POJ3321苹果树：         思路： 快排变形：         思路： POJ2352：星星         思

目录 今天知识点 求交点转化求逆序对，每次操作都维护一个y点的前缀和 树的变动转化成一维数组的变动，利用时间戳将节点转化成区间 先将y排序，然后每加入一个就点更新求一次前缀和 POJ3067：日本 思路： POJ3321苹果树： 思路： POJ2352：星星 思路：                   POJ3067：日本 东海岸有n个城市，西海岸有m个城市，每个海

这道题本身不难，就是一个线状数组求逆序数的简化。一开始没看清题，题目是按升序输入的，先按y在按x已经升序输入了，所以只要考虑x的大小即可，那么简单，直接线状数组走起。但是这里我第一次碰到了做ACM最不愿意碰到的事–超时，上网查了一下，发现算法明明一样，但他们的能过，最后终于发现了问题和解决方案。 因为不需要离散化，update中不能到n，那么就干脆一直计算到maxn，所以这里是要花很多的时间的，