Design Most Recently Used Queue

class BinaryIndexedTree {
private:
    vector<int> bit;

public:
    BinaryIndexedTree(int sz) : bit(sz + 1, 0) {}

    int prefixSum(int idx) {
        int total = 0;
        while (idx > 0) {
            total += bit[idx];
            idx &= idx - 1;
        }
        return total;
    }

    void update(int idx, int val) {
        idx += 1;
        while (idx < bit.size()) {
            bit[idx] += val;
            idx += idx & -idx;
        }
    }
};

class RecentlyUsedQueue {
private:
    int currSize;
    BinaryIndexedTree fenwick;
    vector<int> elements;

public:
    RecentlyUsedQueue(int n) : currSize(n), fenwick(n + 2000), elements(n + 2000, 0) {
        for (int i = 0; i < n; ++i) {
            fenwick.update(i, 1);
            elements[i] = i + 1;
        }
    }

    int fetchElement(int k) {
        int start = 0, end = currSize;
        while (start < end) {
            int middle = (start + end) / 2;
            if (fenwick.prefixSum(middle) < k) {
                start = middle + 1;
            } else {
                end = middle;
            }
        }

        fenwick.update(start - 1, -1);
        fenwick.update(currSize, 1);
        elements[currSize] = elements[start - 1];
        currSize++;

        return elements[start - 1];
    }
};

The provided C++ implementation details a custom data structure called RecentlyUsedQueue, which, simulating a queue where the most recently used elements are tracked uniquely. This class utilizes the BinaryIndexedTree class for efficient range queries and updates, supporting operations that adapt to changes in element access patterns.

• Overview of BinaryIndexedTree Class:

  • Constructed with a size, initializing a vector to track elements using a 1-based index for ease of operations.
  • prefixSum function calculates the cumulative frequency up to an index, useful for determining the position of an element based on its 'used' status.
  • update function modifies the value at a given index, adjusting all relevant entries in the binary indexed tree structure for maintaining correct prefix sums, supporting both addition and removal of frequencies.

• Functionality of RecentlyUsedQueue Class:

  • Initialized with a specified size, this class utilizes both a binary indexed tree and a vector to manage the elements efficiently.
  • Constructor sets up the initial state, where each position is marked as used ('1' in the tree) and elements are filled sequentially.
  • fetchElement function performs the following:
    1. Locate the k-th least recently used element using a binary search on the prefix sums of the tree to find the correct position.
    2. Update the tree to reflect that this element has been used, reducing its frequency at its original position and increasing at the new end position.
    3. Adjust the list of elements to move the accessed element to the end, marking it as recently used.
    4. Return the accessed element, effectively simulating a queue prioritizing recent usage.

The combination of the binary indexed tree and dynamic array manipulation within the RecentlyUsedQueue provides an efficient mechanism to simulate operations on a queue prioritizing elements based on their recent usage, which can be particularly useful in scenarios requiring quick access and updates to a set of elements based on dynamic conditions.

class BinaryIndexedTree {

    private int[] bit;

    public BinaryIndexedTree(int capacity) {
        this.bit = new int[capacity + 1];
    }

    public int prefixSum(int index) {
        int sum = 0;
        while (index > 0) {
            sum += bit[index];
            index &= index - 1;
        }
        return sum;
    }

    public void update(int index, int delta) {
        index += 1;
        while (index < bit.length) {
            bit[index] += delta;
            index += index & -index;
        }
    }
}

class RecentQueue {

    private int currentSize;
    private BinaryIndexedTree fenwick;
    private int[] elements;

    public RecentQueue(int n) {
        this.currentSize = n;
        this.fenwick = new BinaryIndexedTree(n + 2000);
        this.elements = new int[n + 2000];
        for (int i = 0; i < n; ++i) {
            this.fenwick.update(i, 1);
            this.elements[i] = i + 1;
        }
    }

    public int fetch(int k) {
        int low = 0, high = currentSize;
        while (low < high) {
            int mid = (low + high) / 2;
            if (this.fenwick.prefixSum(mid) < k) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }

        this.fenwick.update(low - 1, -1);
        this.fenwick.update(currentSize, 1);
        this.elements[currentSize] = this.elements[low - 1];
        this.currentSize++;

        return this.elements[low - 1];
    }
}

The Java implementation provided consists of two main classes: BinaryIndexedTree and RecentQueue. The BinaryIndexedTree, often known as a Fenwick Tree, helps to efficiently handle updates and compute prefix sums over a range of values, powering the primary operations within RecentQueue.

• In the BinaryIndexedTree class:

  • An array bit is used to store the tree elements.
  • The prefixSum method computes the prefix sum up to a given index by iteratively adding the value at the index and moving to the next segment by clearing the least significant bit.
  • The update method modifies the array by adding a value (delta) to a particular index and adjusts all the relevant subsequent indices efficiently using bit manipulation.

• The RecentQueue class models the Most Recently Used (MRU) Queue:

  • It utilizes the BinaryIndexedTree to efficiently manage the order of elements based on their usage.
  • The elements array holds the actual values in the queue, while the Fenwick Tree tracks their current usage frequency/status.
  • The fetch method retrieves the k-th least recently used item, modifies the corresponding Fenwick Tree entries to mark the fetched item as the most recently used, and adjusts the queue accordingly.

The integration of the BinaryIndexedTree within the RecentQueue ensures that both the update of items' states (after they are accessed) and the retrieval operations are completed efficiently. This design allows for effective handling of dynamically altering access frequencies typical in MRU queues, making it suitable for scenarios where such retrieval patterns are common, like caching mechanisms and memory management.

class BinaryIndexedTree:
    def __init__(self, length):
        self.data = [0] * (length + 1)

    def compute_sum(self, idx):
        accum = 0
        while idx > 0:
            accum += self.data[idx]
            idx -= idx & (-idx)
        return accum

    def update(self, idx, val):
        idx += 1
        while idx < len(self.data):
            self.data[idx] += val
            idx += idx & -idx


class MostRecentUsedQueue:
    def __init__(self, count):
        self.count = count
        self.bi_tree = BinaryIndexedTree(count + 2000)
        self.elements = [0] * (count + 2000)
        for i in range(count):
            self.bi_tree.update(i, 1)
            self.elements[i] = i + 1

    def fetch(self, position):
        start = 0
        end = self.count
        while start < end:
            middle = (start + end) // 2
            if self.bi_tree.compute_sum(middle) < position:
                start = middle + 1
            else:
                end = middle

        modified_position = start - 1
        self.bi_tree.update(modified_position, -1)
        self.bi_tree.update(self.count, 1)
        self.elements[self.count] = self.elements[modified_position]
        self.count += 1

        return self.elements[modified_position]

The given Python code outlines an implementation of a Most Recently Used (MRU) Queue using a Binary Indexed Tree (BIT) or Fenwick Tree for efficient operations. This design helps achieve faster operations particularly useful for scenarios where elements that are more recently accessed need to be retrieved quicker than others.

Solution Overview:

• BinaryIndexedTree class:

  • Initializes a BIT with a given length.
  • compute_sum() method calculates the prefix sum up to a certain index, aiding in range sum queries.
  • update() method adjusts the value at an index which helps in keeping track of access frequency of queue elements.

• MostRecentUsedQueue class:

  • Initializes the queue with a specific number of elements and sets up the BIT with additional space to accommodate future operations.
  • Initially, elements are indexed and updated in the BIT to mark their existence.
  • The fetch() method retrieves the element at the specified position from the queue, considered as the most recently accessed:
    1. It uses a binary search approach powered by the BIT to find the exact position of the fetch quickly.
    2. Adjusts BIT and repositions the fetched element to the end of the queue, marking it as most recently used.
    3. Updates necessary indices in the BIT to reflect this change ensuring all operations remain efficient.

This approach allows the Most Recently Used Queue to handle operations efficiently, making it suitable for applications where frequent access and updates to the most recently accessed items are necessary, maintaining a good balance between time complexity and operational efficiency.