TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
heavy_light_decomposition.cpp File Reference

Heavy Light Decomposition implementation More...

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstring>
#include <iostream>
#include <list>
#include <numeric>
#include <string>
#include <vector>
Include dependency graph for heavy_light_decomposition.cpp:

Go to the source code of this file.

Classes

class  range_queries::heavy_light_decomposition::Tree< X >
 A Basic Tree, which supports binary lifting. More...
class  range_queries::heavy_light_decomposition::SG< X >
 Segment Tree, to store heavy chains. More...
class  range_queries::heavy_light_decomposition::HLD< X >
 The Heavy-Light Decomposition class. More...

Namespaces

namespace  range_queries
 for std::vector
namespace  heavy_light_decomposition
 Heavy light decomposition algorithm.

Functions

static void test_1 ()
static void test_2 ()
static void test_3 ()
int main ()

Detailed Description

Heavy Light Decomposition implementation

Author
Aniruthan R

Heavy-Light Decomposition is a technique on trees, that supports the following:

  1. Update node s, with a value v
  2. Return the (sum) of all node values on the simple path from a to b (sum) can also be replced with XOR, OR, AND, min, or max

The update is done in O(log n) time, and the query is done in O(log^2 n) time with HLD where, n is the number of nodes

The template type is the data type of the value stored in the nodes. If a non-primitive data-type is used as a template, the coressponding operators must be overloaded.

An HLD object can only be created with a constant number of nodes, and it cannot be changed later. Creaty an empty instance is not supported.

To start answering updates and queries,

  1. Create an instance of HLD<X> object (obj), with the required data type.
  2. Read in the edge/parent information and update it with obj.add_edge(). Note: The edges addes must be 0 indexed.
  3. Create a vector with initial node values, and call set_node_val() with it.
  4. Call obj.init() to populate the required information for supporting operations.
  5. Call obj.update(node, new_val), to update the value at index 'node' to the new value. Note: node must be 0 indexed
  6. Call obj.query(a, b) to get the (sum) of node values in the simple path from a to b. Note: a and b, must be 0 indexed.

Sample I/O at the bottom.

Todo
Support edge weight queries, by storing the edge weight value in it's child algorithm verified by testing in CSES path queries: https://cses.fi/problemset/task/1138

Definition in file heavy_light_decomposition.cpp.

Function Documentation

◆ main()

int main ( void )

Main function

Definition at line 641 of file heavy_light_decomposition.cpp.

641 {
642 test_1();
643 test_2();
644 test_3();
645 return 0;
646}
static void test_1()
static void test_2()
static void test_3()

◆ test_1()

void test_1 ( )
static

Test implementations

Returns
none

Definition at line 511 of file heavy_light_decomposition.cpp.

511 {
512 std::cout << "Test 1:\n";
513
514 // Test details
515 int n = 5;
516 std::vector<int64_t> node_values = {4, 2, 5, 2, 1};
517 std::vector<std::vector<int>> edges = {{1, 2}, {1, 3}, {3, 4}, {3, 5}};
518 std::vector<std::vector<int>> queries = {
519 {2, 1, 4},
520 {1, 3, 2},
521 {2, 1, 4},
522 };
523 std::vector<int> expected_result = {11, 8};
524 std::vector<int> code_result;
525
527 hld.set_node_val(node_values);
528 for (int i = 0; i < n - 1; i++) {
529 int u = edges[i][0], v = edges[i][1];
530 hld.add_edge(u - 1, v - 1);
531 }
532 hld.init();
533 for (const auto &q : queries) {
534 int type = q[0];
535 if (type == 1) {
536 int p = q[1], x = q[2];
537 hld.update(p - 1, x);
538 } else if (type == 2) {
539 int a = q[1], b = q[2];
540 code_result.push_back(hld.query(a - 1, b - 1));
541 } else {
542 continue;
543 }
544 }
545 for (int i = 0; i < static_cast<int>(expected_result.size()); i++) {
546 assert(expected_result[i] == code_result[i]);
547 }
548 std::cout << "\nTest 1 passed!\n";
549}

◆ test_2()

void test_2 ( )
static

Second test implementations

Returns
void

Definition at line 555 of file heavy_light_decomposition.cpp.

555 {
556 std::cout << "Test 2:\n";
557
558 // Test details (Bamboo)
559 int n = 10;
560 std::vector<int64_t> node_values = {1, 8, 6, 8, 6, 2, 9, 2, 3, 2};
561 std::vector<std::vector<int>> edges = {{10, 5}, {6, 2}, {10, 7},
562 {5, 2}, {3, 9}, {8, 3},
563 {1, 4}, {6, 4}, {8, 7}};
564 std::vector<std::vector<int>> queries = {
565 {2, 1, 10}, {2, 1, 6}, {1, 3, 4}, {2, 1, 9}, {1, 5, 3},
566 {1, 7, 8}, {2, 1, 4}, {2, 1, 8}, {1, 1, 4}, {1, 2, 7}};
567 std::vector<int> expected_result = {27, 11, 45, 9, 34};
568 std::vector<int> code_result;
569
571 hld.set_node_val(node_values);
572 for (int i = 0; i < n - 1; i++) {
573 int u = edges[i][0], v = edges[i][1];
574 hld.add_edge(u - 1, v - 1);
575 }
576 hld.init();
577 for (const auto &q : queries) {
578 int type = q[0];
579 if (type == 1) {
580 int p = q[1], x = q[2];
581 hld.update(p - 1, x);
582 } else if (type == 2) {
583 int a = q[1], b = q[2];
584 code_result.push_back(hld.query(a - 1, b - 1));
585 } else {
586 continue;
587 }
588 }
589 for (int i = 0; i < static_cast<int>(expected_result.size()); i++) {
590 assert(expected_result[i] == code_result[i]);
591 }
592 std::cout << "\nTest2 passed!\n";
593}

◆ test_3()

void test_3 ( )
static

Third test implementations

Returns
void

Definition at line 599 of file heavy_light_decomposition.cpp.

599 {
600 std::cout << "Test 3:\n";
601
602 // Test details
603 int n = 8;
604 std::vector<int64_t> node_values = {1, 8, 6, 8, 6, 2, 9, 2};
605 std::vector<std::vector<int>> edges = {{1, 2}, {2, 3}, {3, 4}, {1, 5},
606 {6, 3}, {7, 5}, {8, 7}};
607 std::vector<std::vector<int>> queries = {
608 {2, 6, 8}, {2, 3, 6}, {1, 3, 4}, {2, 7, 1}, {1, 5, 3},
609 {1, 7, 8}, {2, 6, 4}, {2, 7, 8}, {1, 1, 4}, {1, 2, 7}};
610 std::vector<int> expected_result = {34, 8, 16, 14, 10};
611 std::vector<int> code_result;
612
614 hld.set_node_val(node_values);
615 for (int i = 0; i < n - 1; i++) {
616 int u = edges[i][0], v = edges[i][1];
617 hld.add_edge(u - 1, v - 1);
618 }
619 hld.init();
620 for (const auto &q : queries) {
621 int type = q[0];
622 if (type == 1) {
623 int p = q[1], x = q[2];
624 hld.update(p - 1, x);
625 } else if (type == 2) {
626 int a = q[1], b = q[2];
627 code_result.push_back(hld.query(a - 1, b - 1));
628 } else {
629 continue;
630 }
631 }
632 for (int i = 0; i < static_cast<int>(expected_result.size()); i++) {
633 assert(expected_result[i] == code_result[i]);
634 }
635 std::cout << "\nTest3 passed!\n";
636}