There's a gap in my knowledge of algorithms for counting problems. How do you count subarrays with sum at most k / at least k if negative numbers are allowed? Can it be done faster than O(n^2)?

Someone showed me how to fill the gaps in my table in O(n log n) time. The idea is to use prefix sums + a self-balancing BST