Leetcode 327: Count of region sum

July 1, 2018

Introduction

It is hard level algorithm called count of region sum. I like to spend 30 minutes on this algorithm first before I go out to play some tennis. I like to spend 20 minutes to read the problem and think about solution first.

Here is the problem statement link.

Now it is 6:28 PM. I spent over 20 minutes to think about it. It may be a dynamic programming solution, and then we try to find all ranges ending at index i, dp[i] stands for the number of ranges in the given range.

Find the solution

It is time for me to find the solution. It is hard for me to come out a complete solution.

It is so exciting to learn something new today.

Here is the idea from one of blogs.

O(n * logn)解法：

解法I 树状数组（Fenwick Tree）：

1. 预处理前n项和数组sums

2. 将sums数组离散化（排序+去重）得到数组osums

3. 遍历sums，记sumi = sums[i]
   用二分查找得到[sumi - upper, sumi - lower]的离散化下标[left, right]
   用树状数组统计范围[left, right]内的元素个数，并累加至最终结果ans
   若lower <= sumi <= upper，额外地令ans+1
   将sumi的离散化下标记入树状数组

上述算法将题目转化为下面的问题：

对于数组sums中的每一个元素sumi，统计出现在sumi左侧，并且数值在[sumi - upper, sumi - lower]范围内的元素个数。
这就等价于统计区间和[0, i]，[1, i]... [i - 1, i]当中所有落在范围[lower, upper]之内的区间个数。

It is so interesting to read the idea how to solve the algorithm in Chinese. I will do some research and see what I can to solve the algorithm.

解法II 归并排序（Merge Sort）：