Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
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:

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

 range_queries
 Algorithms and Data Structures that support range queries and updates.
 
 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

Function Documentation

◆ main()

int main ( void  )

Main function

634  {
635  test_1();
636  test_2();
637  test_3();
638  return 0;
639 }
Here is the call graph for this function:

◆ test_1()

static void test_1 ( )
static

Test implementations

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

◆ test_2()

static void test_2 ( )
static

Second test implementations

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

◆ test_3()

static void test_3 ( )
static

Third test implementations

Returns
void
592  {
593  std::cout << "Test 3:\n";
594 
595  // Test details
596  int n = 8;
597  std::vector<int64_t> node_values = {1, 8, 6, 8, 6, 2, 9, 2};
598  std::vector<std::vector<int>> edges = {{1, 2}, {2, 3}, {3, 4}, {1, 5},
599  {6, 3}, {7, 5}, {8, 7}};
600  std::vector<std::vector<int>> queries = {
601  {2, 6, 8}, {2, 3, 6}, {1, 3, 4}, {2, 7, 1}, {1, 5, 3},
602  {1, 7, 8}, {2, 6, 4}, {2, 7, 8}, {1, 1, 4}, {1, 2, 7}};
603  std::vector<int> expected_result = {34, 8, 16, 14, 10};
604  std::vector<int> code_result;
605 
607  hld.set_node_val(node_values);
608  for (int i = 0; i < n - 1; i++) {
609  int u = edges[i][0], v = edges[i][1];
610  hld.add_edge(u - 1, v - 1);
611  }
612  hld.init();
613  for (const auto &q : queries) {
614  int type = q[0];
615  if (type == 1) {
616  int p = q[1], x = q[2];
617  hld.update(p - 1, x);
618  } else if (type == 2) {
619  int a = q[1], b = q[2];
620  code_result.push_back(hld.query(a - 1, b - 1));
621  } else {
622  continue;
623  }
624  }
625  for (int i = 0; i < static_cast<int>(expected_result.size()); i++) {
626  assert(expected_result[i] == code_result[i]);
627  }
628  std::cout << "\nTest3 passed!\n";
629 }
Here is the call graph for this function:
test_3
static void test_3()
Definition: heavy_light_decomposition.cpp:592
std::vector
STL class.
std::vector::size
T size(T... args)
test_2
static void test_2()
Definition: heavy_light_decomposition.cpp:549
range_queries::heavy_light_decomposition::HLD
The Heavy-Light Decomposition class.
Definition: heavy_light_decomposition.cpp:336
std::vector::push_back
T push_back(T... args)
std::cout
test_1
static void test_1()
Definition: heavy_light_decomposition.cpp:505