第二天叫醒我的不是闹钟,是梦想!
此感悟非对。只要有灵想就写上去。 树状数组求第i个数左右小于它的有几个数。 假设有1 5 2 考虑左边有几个数小于它 那么肯定先放1进去。发现1的左边没有小于它的,所以是0. 再放5进去,发现1在它左边那么5就有一个数小于它。 再放2进去,发现2在1-5之间左边只有一个1小于它,所以也是1.
假设有1 2 5 考虑左边有几个数小于它。 那么肯定先放1进去,发现1的左边没有小于它的,所以是0. 再放2进去,发现2的左边有1,所以答案是1. 再放5进去,发现5的左边有1,2,所以答案为2.
单点修改区间查询: 因为树状数组维护的是前缀和。 所以区间查询的时候 需要c[y]-c[x-1]
区间修改单点查询: 因为树状数组维护的是差分 所以查询的时候直接算一遍当前i的前缀和