AI智能
改变未来

树状数组 java模板(纯代码)

public class TrieNums {int n;/*Nums start from 0*/int[] storage;/*TrieNums index start from 1*/int[] treeNums;int query(int index){int ans = 0;for(int i=index; i > 0; i -= getLowBit(i)) ans += treeNums[i];return ans;}void add(int index, int increase){for(int i = index; i <= n; i += getLowBit(i)) treeNums[i] += increase;}public TrieNums(int[] nums){this.storage = nums;this.n = nums.length;this.treeNums = new int[n + 1];for (int i = 0; i < n; i++) add(i + 1, storage[i]);}public void update(int index, int val){add(index + 1, val - storage[index]);storage[index] = val;}public int sumRange(int left, int right){return query(right +1) - query(left);}public static int getLowBit(int index){return index & (-index);}}

  

赞(0) 打赏
未经允许不得转载:爱站程序员基地 » 树状数组 java模板(纯代码)