Everything about Arrays.

class DynamicArray {
    constructor() {
        this.size = 0;
        this.capacity = 2;
        this.data = new Array(this.capacity);
    }
    
    // Amortized O(1)
    push(element) {
        if (this.size === this.capacity) {
            this.resize();
        }
        this.data[this.size++] = element;
    }
    
    // O(1)
    pop() {
        if (this.size === 0) return undefined;
        const element = this.data[--this.size];
        
        // Shrink if needed
        if (this.size === this.capacity / 4) {
            this.shrink();
        }
        return element;
    }
    
    // O(n)
    resize() {
        this.capacity *= 2;
        const newData = new Array(this.capacity);
        for (let i = 0; i < this.size; i++) {
            newData[i] = this.data[i];
        }
        this.data = newData;
    }
    
    // O(n)
    shrink() {
        this.capacity = Math.floor(this.capacity / 2);
        const newData = new Array(this.capacity);
        for (let i = 0; i < this.size; i++) {
            newData[i] = this.data[i];
        }
        this.data = newData;
    }
}

// Original: [3, 1, 4, 1, 5]
// Prefix:   [3, 4, 8, 9, 14]
// Range Sum(1,3) = prefix[3] - prefix[0] = 9 - 3 = 6

function buildPrefixSum(arr) {
    const prefix = [arr[0]];
    for (let i = 1; i < arr.length; i++) {
        prefix[i] = prefix[i-1] + arr[i];
    }
    return prefix;
}

function rangeSum(prefix, left, right) {
    if (left === 0) return prefix[right];
    return prefix[right] - prefix[left - 1];
}

// For range updates in O(1)
// Add value to range [l, r]
function rangeUpdate(diff, l, r, val) {
    diff[l] += val;
    if (r + 1 < diff.length) {
        diff[r + 1] -= val;
    }
}

// Apply all updates
function applyUpdates(arr, diff) {
    arr[0] += diff[0];
    for (let i = 1; i < arr.length; i++) {
        diff[i] += diff[i-1];
        arr[i] += diff[i];
    }
}