线段树
题目一
给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。
区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。
class Solution {
public int countRangeSum(int[] nums, int lower, int upper) {
long sum = 0; long[] preSum = new long[nums.length + 1]; for (int i = 0; i < nums.length; ++i) {
sum += nums[i]; preSum[i + 1] = sum; } Set<Long> allNumbers = new TreeSet<Long>(); for (long x : preSum) {
allNumbers.add(x); allNumbers.add(x - lower); allNumbers.add(x - upper); } // 利用哈希表进行离散化 Map<Long, Integer> values = new HashMap<Long, Integer>(); int idx = 0; for (long x : allNumbers) {
values.put(x, idx); idx++; } SegNode root = build(0, values.size() - 1); int ret = 0; for (long x : preSum) {
int left = values.get(x - upper), right = values.get(x - lower); ret += count(root, left, right); insert(root, values.get(x)); } return ret; } public SegNode build(int left, int right) {
SegNode node = new SegNode(left, right); if (left == right) {
return node; } int mid = (left + right) / 2; node.lchild = build(left, mid); node.rchild = build(mid + 1, right); return node; } public int count(SegNode root, int left, int right) {
if (left > root.hi || right < root.lo) {
return 0; } if (left <= root.lo && root.hi <= right) {
return root.add; } return count(root.lchild, left, right) + count(root.rchild, left, right); } public void insert(SegNode root, int val) {
root.add++; if (root.lo == root.hi) {
return; } int mid = (root.lo + root.hi) / 2; if (val <= mid) {
insert(root.lchild, val); } else {
insert(root.rchild, val); } } } class SegNode {
int lo, hi, add; SegNode lchild, rchild; public SegNode(int left, int right) {
lo = left; hi = right; add = 0; lchild = null; rchild = null; } } 讯享网
题目二
第一行包含两个整数 n,mn, mn,m，分别表示该数列数字的个数和操作的总个数。
第二行包含 nnn 个用空格分隔的整数，其中第 iii 个数字表示数列第 iii 项的初始值。
接下来 mmm 行每行包含 333 或 444 个整数，表示一个操作，具体如下：
1 x y k：将区间 [x,y][x, y][x,y] 内每个数加上 kkk。2 x y：输出区间 [x,y][x, y][x,y] 内每个数的和。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/117330.html