คู่มือโอลิมปิกคอมพิวเตอร์

Array Manipulation#

คำอธิบาย#

โจทย์กลุ่ม array manipulation คือโจทย์ที่มีข้อมูลเรียงเป็นลำดับ แล้วต้องตอบคำถามหรือแก้ไขค่าในช่วงของ array ให้เร็วกว่าไล่ดูทุกช่องทุกครั้ง

ตัวอย่างคำถามที่พบบ่อย

• หาผลรวมช่วง \lbrack l,r\rbrack

• เพิ่มค่าทุกตำแหน่งในช่วง \lbrack l,r\rbrack

• หาค่าน้อยสุดหรือมากสุดในช่วง

• นับจำนวนค่าที่ตรงเงื่อนไขบางอย่าง

Motivation problem#

ถ้ามี array ขนาด n และมีคำถาม q ครั้ง แต่ละครั้งถามผลรวมตั้งแต่ตำแหน่ง l ถึง r วิธีตรงไปตรงมาคือวนตั้งแต่ l ถึง r

long long sum = 0;
for (int i = l; i <= r; i++) {
  sum += a[i];
}

ถ้าแต่ละ query ใช้เวลา O(n) เวลารวมจะเป็น O(nq) ซึ่งช้าเกินไปเมื่อ n,q มีค่าประมาณ 10^{5}

Prefix sum#

ถ้า array ไม่มีการแก้ไขค่า เราสามารถ preprocess ด้วย prefix sum ได้

pref[0] = 0;
for (int i = 1; i <= n; i++) {
  pref[i] = pref[i - 1] + a[i];
}

ผลรวมช่วง \lbrack l,r\rbrack คือ

pref[r] - pref[l-1]

เวลา preprocess คือ O(n) และตอบแต่ละ query ได้ใน O(1)

Difference array#

ถ้าโจทย์ให้เพิ่มค่า x ทุกตำแหน่งในช่วง \lbrack l,r\rbrack หลายครั้ง แล้วค่อยถามค่า array สุดท้าย ใช้ difference array ได้

diff[l] += x;
diff[r + 1] -= x;

หลังจากทำทุก update แล้ว คำนวณค่าจริงด้วย prefix sum ของ diff

long long cur = 0;
for (int i = 1; i <= n; i++) {
  cur += diff[i];
  a[i] += cur;
}

เทคนิคนี้เหมาะกับโจทย์ offline ที่รู้ update ทั้งหมดก่อนตอบคำถาม

ลองคลิกสองช่องเพื่อดูว่าผลรวมช่วงมาจาก prefix sum สองค่าอย่างไร แล้วเปลี่ยนเป็นโหมด difference array เพื่อเพิ่มค่าทั้งช่วงหลายครั้ง

Prefix sum สองมิติ#

สำหรับตาราง ให้ P[i][j] เป็นผลรวมของสี่เหลี่ยมตั้งแต่ (1,1) ถึง (i,j) ผลรวมของสี่เหลี่ยม \left( r_{1},c_{1} \right) ถึง \left( r_{2},c_{2} \right) หาได้ใน O(1) ด้วยหลัก inclusion-exclusion

for (int i = 1; i <= n; i++)
  for (int j = 1; j <= m; j++)
    P[i][j] = a[i][j] + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1];

long long rect(int r1, int c1, int r2, int c2) {
  return P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1];
}

Fenwick Tree#

Fenwick Tree หรือ Binary Indexed Tree ใช้ตอบ range sum และ point update ได้เร็ว

• update หนึ่งตำแหน่ง: O\left( \log n \right)

• query prefix sum: O\left( \log n \right)

• ใช้หน่วยความจำ O(n)

vector<long long> bit(n + 1);

void add(int idx, long long val) {
  for (; idx <= n; idx += idx & -idx) {
    bit[idx] += val;
  }
}

long long sum(int idx) {
  long long res = 0;
  for (; idx > 0; idx -= idx & -idx) {
    res += bit[idx];
  }
  return res;
}

long long range_sum(int l, int r) {
  return sum(r) - sum(l - 1);
}

ใช้กับโจทย์ Dynamic Range Sum Queries ¹ ได้โดยตรง

Segment Tree#

Segment Tree เหมาะเมื่อ operation ซับซ้อนกว่า sum เช่น min, max, gcd หรือมี range update

• build: O(n)

• query ช่วง: O\left( \log n \right)

• update หนึ่งตำแหน่ง: O\left( \log n \right)

• ใช้หน่วยความจำประมาณ O(4n)

vector<long long> seg(4 * n);

// node เก็บผลรวมของช่วง [l, r] ลูกคือ 2*node และ 2*node+1
void build(int node, int l, int r) {
  if (l == r) {
    seg[node] = a[l];
    return;
  }
  int mid = (l + r) / 2;
  build(node * 2, l, mid);
  build(node * 2 + 1, mid + 1, r);
  seg[node] = seg[node * 2] + seg[node * 2 + 1];
}

void update(int node, int l, int r, int pos, long long val) {  // a[pos] = val
  if (l == r) {
    seg[node] = val;
    return;
  }
  int mid = (l + r) / 2;
  if (pos <= mid) update(node * 2, l, mid, pos, val);
  else update(node * 2 + 1, mid + 1, r, pos, val);
  seg[node] = seg[node * 2] + seg[node * 2 + 1];
}

long long query(int node, int l, int r, int ql, int qr) {  // ผลรวม a[ql..qr]
  if (qr < l || r < ql) return 0;              // ไม่ทับกันเลย
  if (ql <= l && r <= qr) return seg[node];    // อยู่ในช่วงทั้งหมด
  int mid = (l + r) / 2;
  return query(node * 2, l, mid, ql, qr) + query(node * 2 + 1, mid + 1, r, ql, qr);
}
// เรียกใช้: build(1, 1, n); update(1, 1, n, pos, val); query(1, 1, n, l, r);

เปลี่ยน + เป็น min, max หรือ gcd (และค่าที่คืนเมื่อไม่ทับกันเป็น identity ของ operation นั้น) ก็ได้ segment tree สำหรับ operation อื่นทันที

เลือกใช้อะไรดี#

แหล่งฝึก#

• Fenwick Tree ²

• Segment Tree ³

• Visualgo Fenwick Tree ⁴

• Visualgo Segment Tree ⁵

โจทย์ฝึกฝน (Practice Problems)#

ลองทำโจทย์เหล่านี้จาก CSES Problem Set เพื่อฝึกใช้ทักษะจากบทนี้ โดยเริ่มจากโจทย์ที่ง่ายที่สุดก่อน

• Static Range Sum Queries (prefix sum)

• Forest Queries (prefix sum 2 มิติ)

• Subarray Sums I

• Maximum Subarray Sum

• Dynamic Range Sum Queries (Fenwick / segment tree)

• Dynamic Range Minimum Queries (segment tree)

โจทย์เพิ่มเติม: CSES Problem Set และ programming.in.th