วันที่ 13: ต้นไม้เฟนวิคหรือต้นไม้ที่จัดทำดัชนีไบนารี ผลรวมลูกบาศก์

วิกิ: ต้นไม้เฟนวิค หรือ ต้นไม้ที่จัดทำดัชนีไบนารี (BIT) เป็นโครงสร้างข้อมูลที่สามารถอัปเดตองค์ประกอบได้อย่างมีประสิทธิภาพ และคำนวณ ผลรวมคำนำหน้า ใน ตารางตัวเลข

Fenwick Tree หรือที่รู้จักกันในชื่อ Binary Indexed Tree ("BIT") เป็นโครงสร้างข้อมูลที่ให้วิธีที่มีประสิทธิภาพในการสืบค้นช่วงและอัปเดตจุดบนอาร์เรย์ มีประโยชน์อย่างยิ่งสำหรับการแก้ปัญหาที่ต้องใช้ผลรวมสะสมหรือผลรวมคำนำหน้าในอาร์เรย์ที่ไม่แน่นอน

Fenwick Tree ใช้ประโยชน์จากการแสดงเลขฐานสองของจำนวนเต็มและบิตที่มีนัยสำคัญน้อยที่สุด แนวคิดหลักคือการรักษาแผนผังโดยแต่ละโหนดรับผิดชอบช่วงขององค์ประกอบในอาเรย์ดั้งเดิม ช่วยให้สามารถอัปเดตและสืบค้นช่วงได้อย่างมีประสิทธิภาพ

ปัญหา:

การรวมคิวบ์ | HackerRank
กำหนดเมทริกซ์ 3 มิติโดยที่แต่ละบล็อกมี 0 ในตอนแรก บล็อกแรกถูกกำหนดโดยพิกัด (1,1,1) และ...www.hackerrank.com

วิธีแก้ปัญหา (ง่าย ๆ ):

def update_cube(cube, x, y, z, w):
    """
    Update the value of block (x, y, z) to W.
    """
    cube[x][y][z] = w

def query_cube(cube, x1, y1, z1, x2, y2, z2):
    """
    Compute the sum of the values in the cube between the points (x1, y1, z1) and (x2, y2, z2), inclusive.
    """
    total_sum = 0
    for i in range(x1, x2+1):
        for j in range(y1, y2+1):
            for k in range(z1, z2+1):
                total_sum += cube[i][j][k]
    return total_sum

def cubeSum(n, operations):
    """
    Process the given operations and return a list of results.
    """
    results = []
    # Initialize the cube with zeros
    cube = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]
  
    for operation in operations:
        op_type = operation[0]
        if op_type == "UPDATE":
            x, y, z, w = map(int, operation[1:])
            # Subtract 1 from x, y, and z to convert from 1-based indexing to 
            # 0-based indexing
            update_cube(cube, x-1, y-1, z-1, w)
        elif op_type == "QUERY":
            x1, y1, z1, x2, y2, z2 = map(int, operation[1:])
            # Subtract 1 from x1, y1, z1, x2, y2, and z2 to convert from 
            # 1-based indexing to 0-based indexing
            total_sum = query_cube(cube, x1-1, y1-1, z1-1, x2-1, y2-1, z2-1)
            results.append(total_sum)

    return results

คำอธิบาย:

โปรดทราบว่าวิธีแก้ปัญหาง่ายๆ นั้นตรงไปตรงมาอย่างยิ่ง

เราเริ่มต้นลูกบาศก์ด้วยศูนย์

เราตรวจสอบการดำเนินการแต่ละประเภท ขึ้นอยู่กับว่าเป็น UPDATE หรือไม่: เราอัปเดตค่าคิวบ์ที่พิกัดเฉพาะ (x,y,z) หากเป็น QUERY: เราต้องรวมค่าทั้งหมดของพิกัดของคิวบ์

ตัวแปร x1, y1, z1, x2, y2 และ z2 คือพิกัดของมุมที่อยู่ตรงข้ามกันสองมุมของคิวบ์ย่อยที่คุณต้องการคำนวณผลรวมของค่าต่างๆ โดยเฉพาะอย่างยิ่ง (x1, y1, z1) แสดงถึงพิกัด x, y และ z ขั้นต่ำ และ (x2, y2, z2) แสดงถึงพิกัด x, y และ z สูงสุดของคิวบ์ย่อย

map ใช้เพื่อแปลงค่าจาก string เป็น integer

โซลูชันนี้จะทำงานได้ 100% ขึ้นอยู่กับเวลาและกำลังในการคำนวณของคุณ

รายละเอียดรายละเอียดของรหัส:

ฟังก์ชัน update_cube(cube, x, y, z, w): ฟังก์ชันนี้จะอัปเดตค่าของบล็อกที่พิกัด (x, y, z) ที่กำหนดเป็น w
ฟังก์ชัน query_cube(cube, x1, y1, z1, x2, y2, z2): ฟังก์ชันนี้จะคำนวณผลรวมของค่าในคิวบ์ระหว่างจุด (x1, y1, z1) และ (x2, y2, z2) (รวมทั้งคู่) โดยจะใช้ลูปที่ซ้อนกันสามลูปเพื่อวนซ้ำองค์ประกอบทั้งหมดในคิวบ์ย่อยและคำนวณผลรวมของค่าเหล่านั้น
ฟังก์ชัน cubeSum(n, operations): ฟังก์ชันนี้ประมวลผลการดำเนินการที่กำหนดและส่งคืนรายการผลลัพธ์ โดยจะเริ่มต้นลูกบาศก์ 3 มิติด้วยขนาด (n, n, n) และวนซ้ำผ่านการดำเนินการ หากการดำเนินการคือ 'UPDATE' การดำเนินการจะอัพเดตคิวบ์ด้วยค่าใหม่ หากการดำเนินการคือ 'QUERY' ระบบจะคำนวณผลรวมระหว่างพิกัดที่กำหนดโดยใช้ฟังก์ชัน query_cube() และเพิ่มผลลัพธ์ต่อท้ายรายการผลลัพธ์

แนวทางแก้ไข (เฟนวิค):

class FenwickTree3D:
    def __init__(self, n):
        self.size = n
        # Initialize the 3D Fenwick Tree with dimensions (n+1, n+1, n+1) and fill it with zeros
        self.tree = [[[0 for _ in range(n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]

    def update(self, x, y, z, value):
        # Update the Fenwick Tree with the given value at the specified (x, y, z) coordinate
        while x <= self.size:
            y1 = y
            while y1 <= self.size:
                z1 = z
                while z1 <= self.size:
                    self.tree[x][y1][z1] += value
                    z1 += z1 & -z1  # Update z1 index for the next iteration
                y1 += y1 & -y1  # Update y1 index for the next iteration
            x += x & -x  # Update x index for the next iteration

    def query(self, x, y, z):
        # Calculate the sum of values in the cube from the origin (1, 1, 1) to the specified (x, y, z) coordinate
        result = 0
        while x > 0:
            y1 = y
            while y1 > 0:
                z1 = z
                while z1 > 0:
                    result += self.tree[x][y1][z1]
                    z1 -= z1 & -z1  # Update z1 index for the next iteration
                y1 -= y1 & -y1  # Update y1 index for the next iteration
            x -= x & -x  # Update x index for the next iteration
        return result

def cubeSum(n, operations):
    results = []
    # Initialize a 3D Fenwick Tree with size n
    fenwick_tree = FenwickTree3D(n)

    for operation in operations:
        op_type = operation[0]
        if op_type == "UPDATE":
            x, y, z, w = map(int, operation[1:])
            # Calculate the previous value at the given coordinate
            prev_value = fenwick_tree.query(x, y, z) - fenwick_tree.query(x - 1, y, z) - \
                         fenwick_tree.query(x, y - 1, z) - fenwick_tree.query(x, y, z - 1) + \
                         fenwick_tree.query(x - 1, y - 1, z) + fenwick_tree.query(x - 1, y, z - 1) + \
                         fenwick_tree.query(x, y - 1, z - 1) - fenwick_tree.query(x - 1, y - 1, z - 1)
            # Update the Fenwick Tree with the difference between the new value and the previous value
            fenwick_tree.update(x, y, z, w - prev_value)
        elif op_type == "QUERY":
            x1, y1, z1, x2, y2, z2 = map(int, operation[1:])
            # Calculate the range sum between the given coordinates using the inclusion-exclusion principle
            total_sum = fenwick_tree.query(x2, y2, z2) - fenwick_tree.query(x1 - 1, y2, z2) - \
                        fenwick_tree.query(x2, y1 - 1, z2) - fenwick_tree.query(x2, y2, z1 - 1) + \
                        fenwick_tree.query(x1 - 1, y1 - 1, z2) + fenwick_tree.query(x1 - 1, y2, z1 - 1) + \
                        fenwick_tree.query(x2, y1 - 1, z1 - 1) - fenwick_tree.query(x1 - 1, y1 - 1, z1 - 1)
            results.append(total_sum)
      return results

ดังที่คุณคงสังเกตเห็นแล้วว่า เรากำลังใช้ OOP (การเขียนโปรแกรมเชิงวัตถุ) สำหรับโซลูชันที่สองนี้

OOP ถูกเลือกเพราะคุณประโยชน์:

encapsulation: โครงสร้างข้อมูลต้นไม้ Fenwick และวิธีการที่เกี่ยวข้อง (อัปเดตและแบบสอบถาม) ถูกห่อหุ้มไว้ภายในคลาส FenwickTree3D วิธีนี้จะช่วยจัดระเบียบโค้ด และข้อมูลและวิธีการจะรวมเข้าด้วยกัน ซึ่งทำให้เข้าใจและบำรุงรักษาได้ง่ายขึ้น

วิธีการ modularity: ช่วยให้คุณสร้างโมดูลแยกต่างหากสำหรับคลาส FenwickTree3D คุณสามารถใช้โมดูลนี้ซ้ำในปัญหาหรือโครงการอื่นๆ ที่ต้องใช้ 3D Fenwick Tree โดยไม่ต้องแก้ไขการใช้งานหลัก

code clarity: ช่วยทำให้โค้ดอ่านง่ายและเข้าใจง่ายขึ้น คลาสกำหนดอินเทอร์เฟซที่ชัดเจนสำหรับโครงสร้างข้อมูล และวิธีการภายในคลาสมีหน้าที่รับผิดชอบงานเฉพาะที่เกี่ยวข้องกับ Fenwick Tree ทำให้ง่ายต่อการปฏิบัติตามตรรกะของโค้ดและทำความเข้าใจวิธีการใช้โครงสร้างข้อมูล

ทีนี้มาเดินเล่นบนเส้นทางแห่งความทรงจำกัน

การเขียนโปรแกรมเชิงวัตถุ (OOP) เป็นกระบวนทัศน์การเขียนโปรแกรมที่ใช้ "วัตถุ" เพื่อสร้างแบบจำลองเอนทิตีในโลกแห่งความเป็นจริงและการโต้ตอบของพวกมัน ออบเจ็กต์เป็นอินสแตนซ์ของคลาส ซึ่งเป็นเทมเพลตที่กำหนดคุณสมบัติและวิธีการของออบเจ็กต์เหล่านี้

หลักการ:

การห่อหุ้ม: เป็นกระบวนการรวมข้อมูล (คุณสมบัติ) และฟังก์ชัน (วิธีการ) ที่ทำงานกับข้อมูลภายในหน่วยเดียวเรียกว่าคลาส สิ่งนี้จะซ่อนการทำงานภายในของคลาสจากโลกภายนอก และช่วยรักษาความสมบูรณ์ของสถานะของวัตถุ การห่อหุ้มส่งเสริมการแยกข้อกังวล ทำให้โค้ดง่ายต่อการเข้าใจ บำรุงรักษา และแก้ไขข้อบกพร่อง
การสืบทอด: เป็นกลไกที่อนุญาตให้คลาสหนึ่งสืบทอดคุณสมบัติและวิธีการของคลาสอื่น ซึ่งส่งเสริมการนำโค้ดกลับมาใช้ใหม่ได้ คลาสที่สืบทอดมาเรียกว่า “พาเรนต์” หรือ “ซูเปอร์คลาส” และคลาสที่สืบทอดมาเรียกว่า “ชิลด์” หรือ “คลาสย่อย” คลาสย่อยสามารถแทนที่หรือขยายคุณสมบัติและเมธอดของซูเปอร์คลาสได้ ทำให้เกิดพฤติกรรมเฉพาะทางในขณะที่ยังคงได้รับประโยชน์จากฟังก์ชันที่ใช้ร่วมกัน
Polymorphism: หมายถึงความสามารถของวัตถุที่อยู่ในคลาสที่แตกต่างกันที่จะถือว่าเป็นวัตถุของซูเปอร์คลาสทั่วไป ซึ่งช่วยให้อินเทอร์เฟซเดียวสามารถแสดงออบเจ็กต์ประเภทต่างๆ ได้ ทำให้โค้ดมีความยืดหยุ่นและปรับเปลี่ยนได้มากขึ้น ความหลากหลายเกิดขึ้นได้จากการสืบทอดและสามารถมีได้สองรูปแบบ: วิธีการโอเวอร์โหลด (โดยใช้ชื่อวิธีการเดียวกันกับพารามิเตอร์ที่แตกต่างกัน) และการแทนที่วิธีการ (กำหนดวิธีการในคลาสย่อยใหม่)
นามธรรม: เป็นกระบวนการลดความซับซ้อนของระบบที่ซับซ้อนโดยการแบ่งมันออกเป็นส่วนย่อยๆ ที่สามารถจัดการได้มากขึ้น ใน OOP สิ่งนี้สามารถทำได้โดยการสร้างคลาสนามธรรมและอินเทอร์เฟซที่ให้มุมมองที่เรียบง่ายในระดับสูงของระบบในขณะที่ซ่อนรายละเอียดการใช้งานพื้นฐาน Abstraction ช่วยให้นักพัฒนาสามารถมุ่งเน้นไปที่คุณสมบัติที่สำคัญของปัญหาโดยไม่จมอยู่กับความซับซ้อนของระบบ

คำอธิบาย:

Fenwick Tree หรือที่รู้จักในชื่อ Binary Indexed Tree (BIT) เป็นโครงสร้างข้อมูลที่ให้วิธีที่มีประสิทธิภาพในการสืบค้นช่วงและอัปเดตจุดบนอาร์เรย์ มีประโยชน์อย่างยิ่งสำหรับการแก้ปัญหาที่ต้องใช้ผลรวมสะสมหรือผลรวมคำนำหน้าในอาร์เรย์ที่ไม่แน่นอน

Fenwick Tree มีความซับซ้อนด้านเวลาเป็น O(log n) สำหรับทั้งการอัปเดตและการสืบค้นช่วง ซึ่งดีกว่าวิธีไร้เดียงสา O(n) เมื่อดำเนินการหลายอย่างบนอาเรย์ นอกจากนี้ยังประหยัดพื้นที่มากกว่าเมื่อเปรียบเทียบกับโครงสร้างข้อมูลอื่นๆ เช่น แผนผังส่วน

ตอนนี้เรามาดูโค้ดกัน:

FenwickTree3Dclass: เรากำหนดคลาส 3D Fenwick Tree ซึ่งเป็นลักษณะทั่วไปของ 1D Fenwick Tree ตัวสร้างเริ่มต้นต้นไม้ 3 มิติด้วยขนาด (n+1, n+1, n+1) ที่เต็มไปด้วยศูนย์ เราใช้ n+1แทน nเพื่อจัดการการจัดทำดัชนีแบบ 1 สำหรับพิกัดคิวบ์
update()method: วิธีการนี้จะอัปเดตค่า ณ จุดที่กำหนด (x, y, z) ในแผนผัง เราใช้วงวนที่ซ้อนกันเพื่อสำรวจต้นไม้ในแต่ละมิติ ลูปใช้การดำเนินการระดับบิต AND (&) เพื่อกำหนดดัชนีถัดไปที่จะอัปเดต ซึ่งเป็นคุณลักษณะที่สำคัญของ Fenwick Tree
query()method: วิธีนี้จะคำนวณผลรวมของค่าในคิวบ์จากจุดเริ่มต้น (1, 1, 1) ไปยังจุดที่กำหนด (x, y, z) คล้ายกับวิธีการอัปเดต จะใช้การวนซ้ำแบบซ้อนและการดำเนินการระดับบิตเพื่อสำรวจแผนภูมิและสะสมผลรวม
ฟังก์ชัน cubeSum(): ฟังก์ชันนี้ใช้ขนาดของคิวบ์ (n) และรายการการดำเนินการที่จะดำเนินการ โดยจะเริ่มต้นอินสแตนซ์ FenwickTree3D และวนซ้ำในการดำเนินการ หากการดำเนินการเป็น "UPDATE" ระบบจะคำนวณค่าก่อนหน้าที่พิกัดที่กำหนดและอัปเดตแผนภูมิด้วยความแตกต่างระหว่างค่าใหม่และค่าก่อนหน้า หากการดำเนินการคือ "QUERY" ระบบจะคำนวณผลรวมของช่วงโดยใช้วิธีการสืบค้น และใช้ประโยชน์จากหลักการรวม-แยกเพื่อกำหนดผลรวมระหว่างจุดที่กำหนดสองจุดในคิวบ์

สรุป: โซลูชันทั่วไปเทียบกับโซลูชัน Fenwick

Fenwick Tree มีความซับซ้อนของเวลา O(log n) สำหรับทั้งการอัปเดตและการสืบค้นแบบช่วง ซึ่งดีกว่าวิธี naive O(n) เมื่อดำเนินการหลายอย่างบน อาร์เรย์ นอกจากนี้ยังประหยัดพื้นที่มากกว่าเมื่อเปรียบเทียบกับโครงสร้างข้อมูลอื่นๆ เช่น แผนผังส่วน

ขอบคุณสำหรับการอ่านและการสนับสนุนของคุณ

หากมีสิ่งใดไม่ชัดเจนหรือประสบปัญหา โปรดติดต่อที่ "ปานกลาง" หรือ "LinkedIn"

วันที่ 13: ต้นไม้เฟนวิคหรือต้นไม้ที่จัดทำดัชนีไบนารี ผลรวมลูกบาศก์

ปัญหา:

วิธีแก้ปัญหา (ง่าย ๆ ):

คำอธิบาย:

รายละเอียดรายละเอียดของรหัส:

แนวทางแก้ไข (เฟนวิค):

ทีนี้มาเดินเล่นบนเส้นทางแห่งความทรงจำกัน

คำอธิบาย:

สรุป: โซลูชันทั่วไปเทียบกับโซลูชัน Fenwick

ขอบคุณสำหรับการอ่านและการสนับสนุนของคุณ

คำถามในหัวข้อ