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

Function Documentation

main()

int main

(

void

)

Main function

           {
  test_1();
  test_2();
  test_3();
  return 0;
}

Here is the call graph for this function:

test_1()

static void test_1 ( )

static

Test implementations

Returns

none

                     {
  std::cout << "Test 1:\n";
 
  // Test details
  int n = 5;
  std::vector<int64_t> node_values = {4, 2, 5, 2, 1};
  std::vector<std::vector<int>> edges = {{1, 2}, {1, 3}, {3, 4}, {3, 5}};
  std::vector<std::vector<int>> queries = {
      {2, 1, 4},
      {1, 3, 2},
      {2, 1, 4},
  };
  std::vector<int> expected_result = {11, 8};
  std::vector<int> code_result;
 
  range_queries::heavy_light_decomposition::HLD<int64_t> hld(n);
  hld.set_node_val(node_values);
  for (int i = 0; i < n - 1; i++) {
    int u = edges[i][0], v = edges[i][1];
    hld.add_edge(u - 1, v - 1);
  }
  hld.init();
  for (const auto &q : queries) {
    int type = q[0];
    if (type == 1) {
      int p = q[1], x = q[2];
      hld.update(p - 1, x);
    } else if (type == 2) {
      int a = q[1], b = q[2];
      code_result.push_back(hld.query(a - 1, b - 1));
    } else {
      continue;
    }
  }
  for (int i = 0; i < static_cast<int>(expected_result.size()); i++) {
    assert(expected_result[i] == code_result[i]);
  }
  std::cout << "\nTest 1 passed!\n";
}

Here is the call graph for this function:

test_2()

static void test_2 ( )

static

Second test implementations

Returns

void

                     {
  std::cout << "Test 2:\n";
 
  // Test details (Bamboo)
  int n = 10;
  std::vector<int64_t> node_values = {1, 8, 6, 8, 6, 2, 9, 2, 3, 2};
  std::vector<std::vector<int>> edges = {
      {10, 5}, {6, 2}, {10, 7}, {5, 2}, {3, 9}, {8, 3}, {1, 4}, {6, 4}, {8, 7}};
  std::vector<std::vector<int>> queries = {
      {2, 1, 10}, {2, 1, 6}, {1, 3, 4}, {2, 1, 9}, {1, 5, 3},
      {1, 7, 8},  {2, 1, 4}, {2, 1, 8}, {1, 1, 4}, {1, 2, 7}};
  std::vector<int> expected_result = {27, 11, 45, 9, 34};
  std::vector<int> code_result;
 
  range_queries::heavy_light_decomposition::HLD<int64_t> hld(n);
  hld.set_node_val(node_values);
  for (int i = 0; i < n - 1; i++) {
    int u = edges[i][0], v = edges[i][1];
    hld.add_edge(u - 1, v - 1);
  }
  hld.init();
  for (const auto &q : queries) {
    int type = q[0];
    if (type == 1) {
      int p = q[1], x = q[2];
      hld.update(p - 1, x);
    } else if (type == 2) {
      int a = q[1], b = q[2];
      code_result.push_back(hld.query(a - 1, b - 1));
    } else {
      continue;
    }
  }
  for (int i = 0; i < static_cast<int>(expected_result.size()); i++) {
    assert(expected_result[i] == code_result[i]);
  }
  std::cout << "\nTest2 passed!\n";
}

Here is the call graph for this function:

test_3()

static void test_3 ( )

static

Third test implementations

Returns

void

                     {
  std::cout << "Test 3:\n";
 
  // Test details
  int n = 8;
  std::vector<int64_t> node_values = {1, 8, 6, 8, 6, 2, 9, 2};
  std::vector<std::vector<int>> edges = {{1, 2}, {2, 3}, {3, 4}, {1, 5},
                                         {6, 3}, {7, 5}, {8, 7}};
  std::vector<std::vector<int>> queries = {
      {2, 6, 8}, {2, 3, 6}, {1, 3, 4}, {2, 7, 1}, {1, 5, 3},
      {1, 7, 8}, {2, 6, 4}, {2, 7, 8}, {1, 1, 4}, {1, 2, 7}};
  std::vector<int> expected_result = {34, 8, 16, 14, 10};
  std::vector<int> code_result;
 
  range_queries::heavy_light_decomposition::HLD<int64_t> hld(n);
  hld.set_node_val(node_values);
  for (int i = 0; i < n - 1; i++) {
    int u = edges[i][0], v = edges[i][1];
    hld.add_edge(u - 1, v - 1);
  }
  hld.init();
  for (const auto &q : queries) {
    int type = q[0];
    if (type == 1) {
      int p = q[1], x = q[2];
      hld.update(p - 1, x);
    } else if (type == 2) {
      int a = q[1], b = q[2];
      code_result.push_back(hld.query(a - 1, b - 1));
    } else {
      continue;
    }
  }
  for (int i = 0; i < static_cast<int>(expected_result.size()); i++) {
    assert(expected_result[i] == code_result[i]);
  }
  std::cout << "\nTest3 passed!\n";
}

Here is the call graph for this function: