I have data like that:
| Time(seconds from start) | Value |
|---|---|
| 15 | 2 |
| 16 | 4 |
| 19 | 2 |
| 25 | 9 |
There are a lot of entries (10000 ), and I need a way to find fast enough sum of any time range, like sum of range 16-25 seconds (which would be 4 2 9=15). This data will be dynamically changed many times (always adding new entries at the bottom of list).
I am thinking about using sorted list binary search to determinate positions and just make sum of values, but is can took too much time to calculate it. Is there are any more appropriate way to do so? Nuget packets or algorithm references would be appreciated.
CodePudding user response：
Just calculate cumulative sum:
Time Value CumulativeSum
15 2 2
16 4 6
19 2 8
25 9 17
Then for range [16,25] it will be task to binary search left border of 16 and 25 exact, which turns into 17 - 2 = 15
Complexity: O(log(n)), where n - size of the list.
Binary search implementation for lower/upper bound can be found in my repo - https://github.com/eocron/Algorithm/blob/master/Algorithm/Sorted/BinarySearchExtensions.cs