树状数组优化dp

在这里插入图片描述

这个题目怎么去想呢,我们先构造前缀和,一般思路肯定是用两层循环,但是一定会超时,我们的数据范围是 1e5,那我们必须找到复杂度为 nlog n 的才行,所以我们可以考虑每次计算以 i 结尾的子数组的数量,我们只要计算 i 之前的前缀和在 d[i] - upper 和 d[i] - lower 之间的数量,这就需要我们离散化我们的数据

class BIT {
private:
    vector<int> tree;
    int n;

public:
    BIT(int _n): n(_n), tree(_n + 1) {}

    static constexpr int lowbit(int x) {
        return x & (-x);
    }

    void update(int x, int d) {
        while (x <= n) {
            tree[x] += d;
            x += lowbit(x);
        }
    }

    int query(int x) const {
        int ans = 0;
        while (x) {
            ans += tree[x];
            x -= lowbit(x);
        }
        return ans;
    }
};

class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        long long sum = 0;
        vector<long long> preSum = {0};
        for (int v: nums) {
            sum += v;
            preSum.push_back(sum);
        }
        
        set<long long> allNumbers;
        for (long long x: preSum) {
            allNumbers.insert(x);
            allNumbers.insert(x - lower);
            allNumbers.insert(x - upper);
        }
        // 利用哈希表进行离散化
        unordered_map<long long, int> values;
        int idx = 0;
        for (long long x: allNumbers) {
            values[x] = idx;
            idx++;
        }

        int ret = 0;
        BIT bit(values.size());
        for (int i = 0; i < preSum.size(); i++) {
            int left = values[preSum[i] - upper], right = values[preSum[i] - lower];
            ret += bit.query(right + 1) - bit.query(left);
            bit.update(values[preSum[i]] + 1, 1);
        }
        return ret;
    }
};

相关推荐

  1. 数字转换(树形DP

    2024-07-23 09:42:01       25 阅读
  2. 15.动态规划:数据结构优化DP

    2024-07-23 09:42:01       64 阅读
  3. CF1918 D. Blocking Elements [二分+数据结构优化dp]

    2024-07-23 09:42:01       50 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-23 09:42:01       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-23 09:42:01       102 阅读
  3. 在Django里面运行非项目文件

    2024-07-23 09:42:01       83 阅读
  4. Python语言-面向对象

    2024-07-23 09:42:01       92 阅读

热门阅读

  1. uniapp刷新当前页面bug

    2024-07-23 09:42:01       24 阅读
  2. ArcGIS Pro SDK (九)几何 12 多面体

    2024-07-23 09:42:01       21 阅读
  3. 数据库连接池

    2024-07-23 09:42:01       25 阅读
  4. RKNN执行bash ./build-linux_RK3566_RK3568.sh 报错

    2024-07-23 09:42:01       22 阅读
  5. 数学建模--图论与最短路径

    2024-07-23 09:42:01       21 阅读
  6. mariadb安装在服务器(Linux)

    2024-07-23 09:42:01       25 阅读
  7. 银行卡二三四要素核验的多种应用场景

    2024-07-23 09:42:01       28 阅读
  8. 怎么在 Ubuntu 中卸载已经安装的软件

    2024-07-23 09:42:01       23 阅读
  9. ubuntu 源码安装postgis插件

    2024-07-23 09:42:01       28 阅读