Design a Stack With Increment Operation ใน C++ : Stack รองรับ Increment Bottom K Elements

ออกแบบ **CustomStack** รองรับ Operations:

• CustomStack(int maxSize) : กำหนดขนาดสูงสุด
• push(int x) : Push ถ้ายังไม่เต็ม
• pop() : Pop และคืนค่า Top, ว่าง -> -1
• increment(int k, int val) : **บวก val ให้ Bottom k Elements** (ถ้าต่ำกว่า k -> บวกทั้งหมด)

แนวทาง: Lazy Propagation ด้วย Increment Array

แทนที่จะ Loop บวกทุกครั้ง (O(k)) ใช้ **Increment Array inc[]** เก็บ "ค่าที่ต้องบวกสะสม" ต่อ Index

• inc[i] = ค่าที่ต้องบวกให้ Element Index i และ **ทุก Element ข้างล่าง (Bottom)**
• Push: Push ปกติ (ถ้าไม่เต็ม)
• Pop:
  • Top Value = st.back() + inc[topIndex]
  • Propagate: inc[topIndex-1] += inc[topIndex] (ส่งค่าสะสมลงมาข้างล่าง)
  • inc[topIndex] = 0
  • Pop Stack, Return Value
• Increment(k, val):
  • k = min(k, size) - 1 (Index ของ Bottom k-th Element)
  • inc[k] += val (Mark ไว้ ตอน Pop จะ Propagate ลงมา)

**Key Idea:** Increment แค่ Mark ที่ Index k ไว้ ตอน Pop จะ "นำค่าลงมา" ให้ Element ข้างล่างได้ทุกตัวอัตโนมัติ

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class CustomStack {
public:
    vector<int> st;      // Stack values
    vector<int> inc;     // Increment lazy array
    int cap;             // Max size

    CustomStack(int maxSize) {
        cap = maxSize;
        inc = vector<int>(maxSize + 10, 0); // Extra space
    }

    void push(int x) {
        if (st.size() == cap) return;
        st.push_back(x);
    }

    int pop() {
        if (st.empty()) return -1;
        int idx = st.size() - 1;
        int val = st.back() + inc[idx]; // Apply accumulated increment
        st.pop_back();

        // Propagate increment to next element (below)
        if (idx > 0) inc[idx - 1] += inc[idx];
        inc[idx] = 0; // Clear

        return val;
    }

    void increment(int k, int val) {
        k = min(k, (int)st.size()) - 1; // Target index (0-based)
        if (k < 0) return;
        inc[k] += val; // Lazy mark
    }
};

ตัวอย่างการทำงาน

CustomStack(3)
push(1)       // [1]
push(2)       // [1,2]
pop() -> 2    // [1]
push(2)       // [1,2]
push(3)       // [1,2,3]
push(4)       // Ignored (full)
increment(5,100) // inc[2] += 100 (all 3 elements)
increment(2,100) // inc[1] += 100 (bottom 2)
pop() -> 103  // 3 + 100 (from inc[2]) = 103, propagate inc[2] to inc[1] -> inc[1]=200
pop() -> 202  // 2 + 200 = 202
pop() -> 201  // 1 + 200 (inc[0] got from inc[1]) = 201
pop() -> -1   // Empty

ความซับซ้อน (Complexity)

• Push/Pop/Increment: **O(1)** ทุก Operation!
• Space: O(maxSize)

ทำไมทำงานได้? (Why it works)

inc[i] เก็บ "Increment ที่ต้อง Apply ให้ Element Index i และ **ทุก Element ด้านล่าง**" ตอน Pop Index i เรา Apply inc[i] ให้ตัวมัน แล้ว **Push Down** ให้ inc[i-1] (Element ถัดไปด้านล่าง) ทำให้ Element ทั้งหมดด้านล่างได้รับ Increment ครบถ้วนครับ