数状数组模板（板子该记还得记）

数状数组模板（板子该记还得记）

树状数组模板

// 上来先把三个方法写出来
{int[] tree;int lowbit(int x) {return x & -x;}// 查询前缀和的方法int query(int x) {int ans = 0;for (int i = x; i > 0; i -= lowbit(i)) ans += tree[i];return ans;}// 在树状数组 x 位置中增加值 uvoid 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);}
}

本题解题代码

class NumArray {int tree[];int nums[];int n;public int lowBit(int x){return x&-x;}public void add(int x,int val){for(int i=x;i<=n;i+=lowBit(i))tree[i]+=val;}public int query(int x){int ans=0;for(int i=x;i>0;i-=lowBit(i))ans+=tree[i];return ans;}public NumArray(int[] _nums) {nums=_nums;n=nums.length;tree=new int[n+1];for(int i=0;i<nums.length;i++){add(i+1,nums[i]);}}public void update(int index, int val) {add(index+1,val-nums[index]);nums[index]=val;}public int sumRange(int left, int right) {return query(right+1)-query(left);}
}