Put P[N-1], P[N-2], ...P etc. in sorted order into B. When we put a P[i] into B, B only contained P[j]'s with j > i, which takes care of the first condition. We use binary search to find the number of P[j]'s in the valid range for the second condition.
class Solution(object): def countRangeSum(self, A, lower, upper): su = sum(A) B = [su] ans = 0 for x in A[::-1]: su -= x ix = bisect.bisect_left(B, lower+su) jx = bisect.bisect_right(B, upper+su) ans += max(0, jx-ix) bisect.insort(B, su) return ans
Keep in mind bisect.insort has the list insertion which is O(N), but in practice this is fast.