Binary Indexed Tree (Fenwick Tree) solution in Java (Fenwick Tree tutorial link included)


  • 0
    M

    I find this link extremely helpful for understanding Fenwick tree.

    /*
        binary indexed tree (fenwick tree) approach.
        
        input: array in[] of size n
        we make: cumulative frequency array tree[] of size n + 1. tree[0] = 0.
        -- "initialize" can be treated as "update from 0 to nums[i]".
        -- update(i, diff)
            while (i <= n) {
                tree[i] += diff;
                i += (i & -i);
            }
        -- cumulativeSum(i) 
            int sum = 0;
            while (i > 0) {
                sum += tree[i];
                i -= (i & -i);
            }
            return sum;
        --sumRange(i, j)
            return cumulativeSum(j) - cumulativeSum(i - 1);
    */
    public class NumArray {
        
        int[] tree;  // (partial) cumulative frequency array of size n + 1
        int[] numsCopy;  // a copy of the original array nums
        
        private void updateHelper(int idx, int diff) {
            while (idx <= numsCopy.length) {
                tree[idx] += diff;
                idx += (idx & -idx);
            }
        }
        
        private int cumulativeSum(int idx) {
            int sum = 0;
            while (idx > 0) {
                sum += tree[idx];
                idx -= (idx & -idx);
            }
            return sum;
        }
    
        public NumArray(int[] nums) {
            if (nums != null) {
                numsCopy = new int[nums.length];
                for (int i = 0; i < nums.length; ++i) numsCopy[i] = nums[i];
                tree = new int[nums.length + 1];  // partial cumulative sum (binary indexed)
                for (int i = 0; i < nums.length; ++i) updateHelper(i + 1, nums[i]);
            }
        }
    
        void update(int i, int val) {
            updateHelper(i + 1, val - numsCopy[i]);
            numsCopy[i] = val;
        }
    
        public int sumRange(int i, int j) {
            return cumulativeSum(j + 1) - cumulativeSum(i);
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.