当前位置：网站首页>详解树状数组模板——理论和代码的实现

详解树状数组模板——理论和代码的实现

2022-04-22 06:14:00 【shooter7】

树状数组

// 上来先把三个方法写出来
{
    
    int[] tree;
    int lowbit(int x) {
    
        return x & -x;
    }
    // 查询前缀和的方法(包含下标x)
    int query(int x) {
    
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tree[i];
        return ans;
    }
    // 在树状数组 x 位置中增加值 u
    void add(int x, int u) {
    
        for (int i = x; i <= n; i += lowbit(i)) tree[i] += u;
    }
}

// 初始化「树状数组」，要默认数组是从 1 开始
{
    
    for (int i = 0; i < n; i++) add(i + 1, nums[i]);
}

// 使用「树状数组」：
{
       
    void update(int i, int val) {
    
        // 原有的值是 nums[i]，要使得修改为 val，需要增加 val - nums[i]
        add(i + 1, val - nums[i]); 
        nums[i] = val;
    }
    
    int sumRange(int l, int r) {
    
        return query(r + 1) - query(l);
    }
}

版权声明
本文为[shooter7]所创，转载请带上原文链接，感谢
https://blog.csdn.net/shooter7/article/details/123966754

边栏推荐

猜你喜欢

随机推荐