Use the C++ version of standard C header files

You are including <math.h>, but you should include <cmath>. Especially for the math functions, using the versions from std:: will make sure they automatically deduce whether they should return float or double.

Avoid unnecessary use of floating point arithmetic

Converting an integer to floating point, doing some operation, and then converting back is going to be slow. Floating point math is also not always exact, and this can cause problems if you assume it is. If possible, do everything using integer arithmetic where possible.

To see what you can do with just integers, look at Sean Eron Anderson's bit twiddling hacks, it includes how to check if an integer is a power of two and how to round up to the next power of two.

Even better, if you can use C++20, use std::has_single_bit() to check if something is a power of two, and std::bit_ceil() to round up to the nearest power of two.

Unnecessary use of std::shared_ptr

I don't see any reason to use std::shared_ptr for storing Nodes. You should be able to just write:

…
int non_leaves = total_nodes - leaves;
std::vector<Node> nodes(non_leaves);

This creates a vector of non_leaves Nodes. Then to add the leaf nodes:

for (int i = 0; i < leaves; ++i) {
    std::string substr = (i >= str.length()) ? "" : std::string(1, str[i]);
    nodes.emplace_back(DJB2(substr));
}

In the rest of the code, you can replace ->hash with .hash, since the elements of nodes` are no longer pointers.

Use .reserve()

Since STL containers do not know up front how many elements you are going to place in them, they start out small and allocate more memory later, and for std::vector is also has to move elements from the old to the new memory region each time it grows. But if you know up front how many elements you are going to store, you can call .reserve() so it can do one big allocation up front:

std::vector<Node> nodes(…);
nodes.reserve(total_nodes);

Use '\n' instead of std::endl

Prefer to use '\n' instead of std::endl; the are mostly equivalent, but the latter also forces the output to be flushed, which is often unnecessary and can be bad for performance.

Suboptimal calculation of internal node hash values

Regardless of the performance of DJB2() itself, one issue is that for the internal nodes, you are converting indices to strings, concatenating those strings, and then hashing the result of that. That is not efficient, and it also has some issues. For example, consider these scenarios:

• `left_child_hash = "123"; right_child_hash = "45";
• `left_child_hash = "12"; right_child_hash = "345";

The child hashes in the second case are clearly different from the first case, but the concatenation is the same. While hash functions don't guarantee uniqueness, so it's probably not a big problem, you are actually providing less information to the hash function than you could, so it's going to perform slightly worse.

One solution would be to do a bitwise copy of the integers into a std::string and hash that. Making use of the fact that the two child hash values are already consecutive inside nodes:

std::string child_hashes(2 * sizeof(Node));

for (int i = non_leaves - 1; i >= 0; --i) {
    std::copy_n(reinterpret_cast<char*>(&nodes[2 * i + 1]), 2 * sizeof(Node), child_hashes.data());
    nodes[i].hash = DJB2(child_hashes);
}

Make use of std::string_view if possible

It would be nice if DJB2() would take a std::string_view as an argument. This would avoid some copies that your code is currently making, like substr, and even the std::copy_n() into child_hashes in the example above.

Pre-compute commonly used hash values

While the compiler might be able to optimize this for you if it can inline DJB2(), you can help it yourself by pre-computing the hash of the empty string:

Node empty_node{DJB2("")};

for (int i = 0; i < leaves; ++i) {
    if (i >= str.length()) {
        nodes.push_back(empty_node);
    } else {
        nodes.emplace_back(DJB2(str.substr(i, 1)));
    }
}

Or even better, remove the if entirely and just loop up to str.length() and pad the vector afterwards:

for (int i = 0; i < str.length(); ++i) {
    nodes.emplace_back(DJB2(str.substr(i, 1)));
}

nodes.insert(nodes.back(), leaves - str.length(), DJB2(""));

Also note that if str is very large, you will likely calculate the hash of the same character multiple times. You could then speed up this part by pre-computing all possible hashes of a char, or by creating a simple cache.