Welcome to Subscribe On Youtube
327. Count of Range Sum
Description
Given an integer array nums and two integers lower and upper, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j inclusive, where i <= j.
Example 1:
Input: nums = [-2,5,-1], lower = -2, upper = 2 Output: 3 Explanation: The three ranges are: [0,0], [2,2], and [0,2] and their respective sums are: -2, -1, 2.
Example 2:
Input: nums = [0], lower = 0, upper = 0 Output: 1
Constraints:
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 1-105 <= lower <= upper <= 105- The answer is guaranteed to fit in a 32-bit integer.
Solutions
Binary Indexed Tree or Segment Tree.
-
class BinaryIndexedTree { private int n; private int[] c; public BinaryIndexedTree(int n) { this.n = n; this.c = new int[n + 1]; } public void update(int x, int v) { while (x <= n) { c[x] += v; x += x & -x; } } public int query(int x) { int s = 0; while (x != 0) { s += c[x]; x -= x & -x; } return s; } } class Solution { public int countRangeSum(int[] nums, int lower, int upper) { int n = nums.length; long[] s = new long[n + 1]; for (int i = 0; i < n; ++i) { s[i + 1] = s[i] + nums[i]; } long[] arr = new long[n * 3 + 3]; for (int i = 0, j = 0; i <= n; ++i, j += 3) { arr[j] = s[i]; arr[j + 1] = s[i] - lower; arr[j + 2] = s[i] - upper; } Arrays.sort(arr); int m = 0; for (int i = 0; i < arr.length; ++i) { if (i == 0 || arr[i] != arr[i - 1]) { arr[m++] = arr[i]; } } BinaryIndexedTree tree = new BinaryIndexedTree(m); int ans = 0; for (long x : s) { int l = search(arr, m, x - upper); int r = search(arr, m, x - lower); ans += tree.query(r) - tree.query(l - 1); tree.update(search(arr, m, x), 1); } return ans; } private int search(long[] nums, int r, long x) { int l = 0; while (l < r) { int mid = (l + r) >> 1; if (nums[mid] >= x) { r = mid; } else { l = mid + 1; } } return l + 1; } } -
class BinaryIndexedTree { public: BinaryIndexedTree(int _n) : n(_n) , c(_n + 1) {} void update(int x, int v) { while (x <= n) { c[x] += v; x += x & -x; } } int query(int x) { int s = 0; while (x) { s += c[x]; x -= x & -x; } return s; } private: int n; vector<int> c; }; class Solution { public: int countRangeSum(vector<int>& nums, int lower, int upper) { using ll = long long; int n = nums.size(); ll s[n + 1]; s[0] = 0; for (int i = 0; i < n; ++i) { s[i + 1] = s[i] + nums[i]; } ll arr[(n + 1) * 3]; for (int i = 0, j = 0; i <= n; ++i, j += 3) { arr[j] = s[i]; arr[j + 1] = s[i] - lower; arr[j + 2] = s[i] - upper; } sort(arr, arr + (n + 1) * 3); int m = unique(arr, arr + (n + 1) * 3) - arr; BinaryIndexedTree tree(m); int ans = 0; for (int i = 0; i <= n; ++i) { int l = lower_bound(arr, arr + m, s[i] - upper) - arr + 1; int r = lower_bound(arr, arr + m, s[i] - lower) - arr + 1; ans += tree.query(r) - tree.query(l - 1); tree.update(lower_bound(arr, arr + m, s[i]) - arr + 1, 1); } return ans; } }; -
class BinaryIndexedTree: def __init__(self, n): self.n = n self.c = [0] * (n + 1) def update(self, x, v): while x <= self.n: self.c[x] += v x += x & -x def query(self, x): s = 0 while x > 0: s += self.c[x] x -= x & -x return s class Solution: def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int: s = list(accumulate(nums, initial=0)) arr = sorted(set(v for x in s for v in (x, x - lower, x - upper))) tree = BinaryIndexedTree(len(arr)) ans = 0 for x in s: l = bisect_left(arr, x - upper) + 1 r = bisect_left(arr, x - lower) + 1 ans += tree.query(r) - tree.query(l - 1) tree.update(bisect_left(arr, x) + 1, 1) return ans -
type BinaryIndexedTree struct { n int c []int } func newBinaryIndexedTree(n int) *BinaryIndexedTree { c := make([]int, n+1) return &BinaryIndexedTree{n, c} } func (this *BinaryIndexedTree) update(x, delta int) { for x <= this.n { this.c[x] += delta x += x & -x } } func (this *BinaryIndexedTree) query(x int) int { s := 0 for x > 0 { s += this.c[x] x -= x & -x } return s } func countRangeSum(nums []int, lower int, upper int) (ans int) { n := len(nums) s := make([]int, n+1) for i, x := range nums { s[i+1] = s[i] + x } arr := make([]int, (n+1)*3) for i, j := 0, 0; i <= n; i, j = i+1, j+3 { arr[j] = s[i] arr[j+1] = s[i] - lower arr[j+2] = s[i] - upper } sort.Ints(arr) m := 0 for i := range arr { if i == 0 || arr[i] != arr[i-1] { arr[m] = arr[i] m++ } } arr = arr[:m] tree := newBinaryIndexedTree(m) for _, x := range s { l := sort.SearchInts(arr, x-upper) + 1 r := sort.SearchInts(arr, x-lower) + 1 ans += tree.query(r) - tree.query(l-1) tree.update(sort.SearchInts(arr, x)+1, 1) } return } -
class BinaryIndexedTree { private n: number; private c: number[]; constructor(n: number) { this.n = n; this.c = Array(n + 1).fill(0); } update(x: number, v: number) { while (x <= this.n) { this.c[x] += v; x += x & -x; } } query(x: number): number { let s = 0; while (x > 0) { s += this.c[x]; x -= x & -x; } return s; } } function countRangeSum(nums: number[], lower: number, upper: number): number { const n = nums.length; const s = Array(n + 1).fill(0); for (let i = 0; i < n; ++i) { s[i + 1] = s[i] + nums[i]; } let arr: number[] = Array((n + 1) * 3); for (let i = 0, j = 0; i <= n; ++i, j += 3) { arr[j] = s[i]; arr[j + 1] = s[i] - lower; arr[j + 2] = s[i] - upper; } arr.sort((a, b) => a - b); let m = 0; for (let i = 0; i < arr.length; ++i) { if (i === 0 || arr[i] !== arr[i - 1]) { arr[m++] = arr[i]; } } arr = arr.slice(0, m); const tree = new BinaryIndexedTree(m); let ans = 0; for (const x of s) { const l = search(arr, m, x - upper); const r = search(arr, m, x - lower); ans += tree.query(r) - tree.query(l - 1); tree.update(search(arr, m, x), 1); } return ans; } function search(nums: number[], r: number, x: number): number { let l = 0; while (l < r) { const mid = (l + r) >> 1; if (nums[mid] >= x) { r = mid; } else { l = mid + 1; } } return l + 1; }