Hello,

some time ago I was looking on a problem of finding number of subarrays with sum not exceeding a given number K. Numbers in the array can be negative. Right now I'm thinking if there could be an efficient solution that uses a Fenwick tree.

I know about two other solutions, one that is quite straightforward, runs in O(n^2) and uses prefixes. And the second that is an O(n log n) divide and conquer solution that uses sorted prefixes and suffixes, and solves the problem for subarrays that are on the left, on the right and those that are going trough the middle.

I also have a basic knowledge of Fenwick trees and I heard that they might be used to solve this problem. However I don't know how, apart from the fact that one might use Fenwick tree instead of prefixes in the O(n^2) solution which of course isn't very good.

TL;DR How can we use Fenwick tree/s to find number of subarrays with sum less than sum K? Numbers in the given array can be negative.