Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/d2/de9/heavy__light__decomposition_8cpp_source.html below:

TheAlgorithms/C++: range_queries/heavy_light_decomposition.cpp Source File

std::vector<std::list<int>>

std::vector<std::vector<int>>

<

T>

(

&v :

[u]) {

(

[u][k - 1] != -1) {

(

&v :

[u]) {

[u].push_back(v);

[v].push_back(u);

assert(

(node_val.size()) ==

);

(

*

p,

dist) {

(

k =

- 1; k >= 0; k--) {

<

X>

<

T>

X

(X lhs, X rhs) {

lhs + rhs; }

(

size) {

(p +=

; p > 0; p >>= 1) {

(l +=

, r +=

+ 1; l < r; l >>= 1, r >>= 1) {

<

X>

hc_size = -1, hc_id = -1;

(

nodes) :

<X>(nodes),

<X>(nodes) {

(

i = 0; i < Tree<X>::t_nodes; i++) {

std::cout <<

;

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 = {

std::vector<int> expected_result = {11, 8};

std::vector<int> code_result;

(

i = 0; i < n - 1; i++) {

u = edges[i][0], v = edges[i][1];

(

&q : queries) {

p = q[1], x = q[2];

}

(type == 2) {

a = q[1], b = q[2];

code_result.push_back(hld.

(a - 1, b - 1));

(

i = 0; i < static_cast<int>(expected_result.size()); i++) {

assert(expected_result[i] == code_result[i]);

std::cout <<

;

std::cout <<

;

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;

(

i = 0; i < n - 1; i++) {

u = edges[i][0], v = edges[i][1];

(

&q : queries) {

p = q[1], x = q[2];

}

(type == 2) {

a = q[1], b = q[2];

code_result.push_back(hld.

(a - 1, b - 1));

(

i = 0; i < static_cast<int>(expected_result.size()); i++) {

assert(expected_result[i] == code_result[i]);

std::cout <<

;

std::cout <<

;

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;

(

i = 0; i < n - 1; i++) {

u = edges[i][0], v = edges[i][1];

(

&q : queries) {

p = q[1], x = q[2];

}

(type == 2) {

a = q[1], b = q[2];

code_result.push_back(hld.

(a - 1, b - 1));

(

i = 0; i < static_cast<int>(expected_result.size()); i++) {

assert(expected_result[i] == code_result[i]);

std::cout <<

;

The Heavy-Light Decomposition class.

void dfs_labels(int u, int p=-1)

Utility function to lable the nodes so that heavy chains have a contigous lable.

std::vector< int > h_parent

stores the top of the heavy chain from a node

void dfs_par(int u, int p=-1)

Utility function to assign highest parent that can be reached though heavy chains.

X query(int a, int b)

This function returns the sum of node values in the simple path from from node_1 to node_2.

HLD(int nodes)

Class parameterized constructor. Resizes the and initilizes the data members.

int label

utility member to assign labels in dfs_labels()

X chain_query(int a, int b)

Utility function to break down a path query into two chain queries.

std::vector< int > h_heavychlid

stores the heavy child of a node

void update(int node, X val)

This function updates the value at node with val.

std::vector< int > h_label

stores the label of a node

void init()

This function must be called after the tree adjacency list and node values are populated The function...

void dfs_hc(int u, int p=-1)

Utility function to assign heavy child to each node (-1 for a leaf node)

X query(int l, int r)

Make a range query from node label l to node label r.

void update(int p, X v)

Update the value at a node.

X combine(X lhs, X rhs)

Function that specifies the type of operation involved when segments are combined.

X sret_init

inital query return value

int s_size

number of leaves in the segment tree

void set_sret_init(X new_sret_init)

Set the initialization for the query data type, based on requirement.

SG(int size)

Class parameterized constructor. Resizes the and initilizes the data members.

std::vector< X > s_tree

Everything here is private, and can only be accessed through the methods, in the derived class (HLD)

void set_node_val(const std::vector< X > &node_val)

Set the values for all the nodes.

std::vector< int > t_depth

a vector to store the depth of a node,

std::vector< X > t_val

values of nodes

std::vector< std::vector< int > > t_par

a matrix to store every node's 2^kth parent

void add_edge(const int u, const int v)

Adds an undirected edge from node u to node v in the tree.

Tree(int nodes)

Class parameterized constructor, resizes the and initializes the data members.

int kth_ancestor(int p, const int &dist)

The function returns the kth ancestor of a node.

void dfs_size(int u, int p=-1)

Utility function to compute sub-tree sizes.

int t_root

the root of the tree

std::vector< std::list< int > > t_adj

an adjacency list to stores the tree edges

const int t_maxlift

maximum possible height of the tree

void change_root(int new_root)

Set the root for the tree.

void lift(int *const p, int dist)

The function lifts a node, k units up the tree. The lifting is done in place, and the result is store...

void init()

This function must be called after the tree adjacency list and node values are populated The function...

std::vector< int > t_size

a vector to store the subtree size rooted at node

int lca(int a, int b)

The function returns the least common ancestor of two nodes.

const int t_nodes

number of nodes

void dfs_lca(int u, int p=-1)

Utility function to populate the t_par vector.

Heavy light decomposition algorithm.

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4