SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The NumArray class is designed to handle two main operations efficiently on a list of integers: updating an element at a specific index and calculating the sum of elements within a given range. The implementation utilizes a Binary Indexed Tree (BIT) to achieve these operations in logarithmic time, making it suitable for scenarios where frequent updates and sum queries are required.

Intuition

A Binary Indexed Tree (BIT) is an advanced data structure that allows efficient updates and prefix sum calculations. The intuition behind using a BIT is to maintain a tree-like structure where each node stores the cumulative sum of a subset of the array elements. This structure allows both update and sum operations to be performed in (O(\log n)) time, where (n) is the number of elements in the array. The BIT is particularly effective when there are multiple range sum queries and updates, as it significantly reduces the time complexity compared to a naive approach.

Approach

1. BIT Initialization:

   • The BIT class is initialized with an array size of (N + 1), where (N) is the length of the input array. The additional element accounts for the 1-based indexing required by the BIT operations.

2. Increase Operation:

   • The increase(i, x) method updates the BIT by adding the value (x) to the (i)-th index and all of its relevant ancestors in the tree. This is done by manipulating the index using the operation i |= (i + 1) to move to the next relevant node.

3. Total Operation:

   • The total(i) method calculates the prefix sum from the start of the array to the (i)-th index by traversing the tree from the (i)-th index backward, accumulating the values stored in the relevant nodes.

4. NumArray Class:

   • The NumArray class initializes the BIT and populates it with the initial values of the input array using the increase method.
   • The update(index, val) method adjusts the value at a specific index by calculating the difference (delta) between the new value and the current value, then applying this difference using the BIT's increase method.
   • The sumRange(left, right) method computes the sum of the elements between the left and right indices by utilizing the BIT's total method to get the prefix sums and subtracting the results accordingly.

Complexity

Time Complexity:

Both the update and sum range operations run in (O(\log n)) time, where (n) is the number of elements in the array. This efficiency is achieved due to the logarithmic height of the Binary Indexed Tree.

Space Complexity:

The space complexity is (O(n)) for storing the BIT array, where (n) is the length of the input array. This additional space is required to maintain the tree structure that supports efficient updates and queries.

Code

C++

class BIT {
private:
    std::vector<int> stree;
public:
    BIT(int N) {
        stree = std::vector<int>(N + 1, 0);
    }

    void increase(int i, int x) {
        while (i < stree.size()) {
            stree[i] += x;
            i |= (i + 1);
        }
    }

    int total(int i) {
        int sum = 0;
        while (i >= 0) {
            sum += stree[i];
            i = (i & (i + 1)) - 1;
        }
        return sum;
    }
};

class NumArray {
private:
    BIT bit;
    std::vector<int> nums;
public:
    NumArray(std::vector<int>& nums) : bit(nums.size()), nums(nums) {
        for (int i = 0; i < nums.size(); i++) {
            bit.increase(i + 1, nums[i]);
        }
    }

    void update(int index, int val) {
        int delta = val - nums[index];
        bit.increase(index + 1, delta);
        nums[index] += delta;
    }

    int sumRange(int left, int right) {
        return bit.total(right + 1) - bit.total(left);
    }
};

Python

class BIT:
    def __init__(self, N):
        self.stree = [0] * (N + 1)

    def increase(self, i, x):
        while i < len(self.stree):
            self.stree[i] += x
            i |= (i + 1)

    def total(self, i):
        sum = 0
        while i >= 0:
            sum += self.stree[i]
            i = (i & (i + 1)) - 1
        return sum

class NumArray:
    def __init__(self, nums):
        self.bit = BIT(len(nums))
        self.nums = nums
        for i in range(len(nums)):
            self.bit.increase(i + 1, nums[i])

    def update(self, index, val):
        delta = val - self.nums[index]
        self.bit.increase(index + 1, delta)
        self.nums[index] += delta

    def sumRange(self, left, right):
        return self.bit.total(right + 1) - self.bit.total(left)

Java

class BIT {
    private int[] stree;

    public BIT(int N) {
        stree = new int[N + 1];
    }

    public void increase(int i, int x) {
        while (i < stree.length) {
            stree[i] += x;
            i |= (i + 1);
        }
    }

    public int total(int i) {
        int sum = 0;
        while (i >= 0) {
            sum += stree[i];
            i = (i & (i + 1)) - 1;
        }
        return sum;
    }
}

class NumArray {
    private BIT bit;
    private int[] nums;

    public NumArray(int[] nums) {
        bit = new BIT(nums.length);
        this.nums = nums;
        for (int i = 0; i < nums.length; i++) {
            bit.increase(i + 1, nums[i]);
        }
    }

    public void update(int index, int val) {
        int delta = val - nums[index];
        bit.increase(index + 1, delta);
        nums[index] += delta;
    }

    public int sumRange(int left, int right) {
        return bit.total(right + 1) - bit.total(left);
    }
}

JavaScript

class BIT {
    constructor(N) {
        this.stree = new Array(N+1).fill(0)
    }
    increase(i, x) {
        while(i < this.stree.length) {
            this.stree[i] += x
            i |= (i+1)
        }
    }
    
    total(i) {
        let sum = 0
        
        while(i >= 0) {
            sum += this.stree[i]
            i &= i + 1
            i -= 1
        }
        
        return sum
    }
}
var NumArray = function(nums) {
    this.bit = new BIT(nums.length)
    
    for(let i = 0; i < nums.length; i++) {
        const curr = nums[i]
        
        this.bit.increase(i + 1, curr)
    }
    
    this.nums = nums
};

/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
NumArray.prototype.update = function(index, val) {
    const delta = val - this.nums[index]
    
    this.bit.increase(index + 1, delta)
    this.nums[index] += delta
};

NumArray.prototype.sumRange = function(left, right) {
    return this.bit.total(right + 1) - this.bit.total(left)
};