## c++ – Not getting required answer in my segment tree implementation

#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define MOD 1000000007
#define testcase lli t;cin>>t;while(t--)
#define fast_io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pb push_back
#define PB pop_back
#define P pair<int,int>


I dont understand why the array ‘tree’ is giving me answer 0 even though the value is getting stored in through makeTree method in segmentTree class.

int a(1000000),tree(1000000);
class segmentTree{
private:
int n;
public:
segmentTree(int a)
{
n=a;
}
void makeTree(int ind, int low, int high)
{
if(low==high)
{
tree(ind) = a(low);
return;
}
int mid=(low+high)/2;
makeTree((2*ind)+1,low,mid);
makeTree((2*ind)+2,mid+1,high);
tree(ind) = a((2*ind)+1)+a((2*ind)+2);
}
int sum(int a,int b)
{
a+=(n);
b+=(n);
int sum=0;
while(a<=b)
{
if(a%2==1)
{
sum+=tree(a-1);
a++;
}
if(b%2==0)
{
sum+=tree(b-1);
b--;
}
a/=2;
b/=2;
}
return sum;
}
};
void solve()
{
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++)
{
cin>>a(i);
}
segmentTree st(n);
st.makeTree(0,0,n-1);
for(int i=0;i<2*n;i++)
{
cout<<tree(i)<<" ";
}
}
int main()
{
testcase{
solve();
}
}


## recursion – An arithmetic_mean Function For Various Type Arbitrary Nested Iterable Implementation in C++

This is a follow-up question for A recursive_count Function For Various Type Arbitrary Nested Iterable Implementation in C++ and A Summation Function For Boost.MultiArray in C++. I am trying to implement an arithmetic_mean template function for calculating the arithmetic mean value of various type arbitrary nested iterable things. The recursive_reduce function (thanks to G. Sliepen’s answer) and the recursive_size function are used here. Because both recursive_reduce function and recursive_size function are needed in the arithmetic_mean function here, there are two new concepts is_recursive_reduceable and is_recursive_sizeable created as follows.

template<typename T>
concept is_recursive_reduceable = requires(T x)
{
recursive_reduce(x, 0.0);
};

template<typename T>
concept is_recursive_sizeable = requires(T x)
{
recursive_size(x);
};


Next, the main part of arithmetic_mean template function:

template<class T> requires (is_recursive_reduceable<T> && is_recursive_sizeable<T>)
auto arithmetic_mean(const T& input)
{
return (recursive_reduce(input, 0.0)) / (recursive_size(input));
}


Some test cases of this arithmetic_mean template function.

//  std::vector<int> case
std::vector<int> test_vector = {
1, 2, 3
};
auto arithmetic_mean_result1 = arithmetic_mean(test_vector);
std::cout << arithmetic_mean_result1 << std::endl;

//  std::vector<std::vector<int>> case
std::vector<decltype(test_vector)> test_vector2 = {
test_vector, test_vector, test_vector
};
auto arithmetic_mean_result2 = arithmetic_mean(test_vector2);
std::cout << arithmetic_mean_result2 << std::endl;

// std::deque<int> case
std::deque<int> test_deque;
test_deque.push_back(1);
test_deque.push_back(1);
test_deque.push_back(1);
auto arithmetic_mean_result3 = arithmetic_mean(test_deque);
std::cout << arithmetic_mean_result3 << std::endl;

// std::deque<std::deque<int>> case
std::deque<decltype(test_deque)> test_deque2;
test_deque2.push_back(test_deque);
test_deque2.push_back(test_deque);
test_deque2.push_back(test_deque);
auto arithmetic_mean_result4 = arithmetic_mean(test_deque2);
std::cout << arithmetic_mean_result4 << std::endl;


All suggestions are welcome.

The summary information:

## c – Use of globals in stack-based virtual machine implementation

Usage of globals is a matter of scope of the program “around” them.

If this “stack-based virtual machine” is the whole program, and the statement “…variables are used by pretty much every function” is literally true (and not an exaggeration), then making those variables global is perfectly fine.

However, if this “stack-based virtual machine” is just a module of a larger program, I would recommend against making the mentioned variables globally visible.

In case the “stack-based virtual machine” is starting as one program, and becoming a module of a larger program at a later point in time, one should take the time and refactor any “globals” as soon as the second case can be foreseen.

## recursion – A recursive_count_if Function with Automatic Type Deducing from Lambda for Various Type Arbitrary Nested Iterable Implementation in C++

This is a follow-up question for A recursive_count_if Function For Various Type Arbitrary Nested Iterable Implementation in C++ and A recursive_count_if Function with Specified value_type for Various Type Arbitrary Nested Iterable Implementation in C++. After digging into the thing that detecting the argument type of a function, I found that it is possible to simplify the T1 parameter in last implementation with boost::callable_traits::args_t syntax in Boost.CallableTraits library. As the result, recursive_count_if template function can be used exactly as the following code.

std::vector<std::vector<std::string>> v = {{"hello"}, {"world"}};
auto size5 = ()(std::string s) { return s.size() == 5; };
auto n = recursive_count_if(v, size5);


The implementation of recursive_count_if function with automatic type deducing:

#include <boost/callable_traits.hpp>
//  recursive_count_if implementation
template<class T1, class T2> requires (is_iterable<T1> && std::same_as<std::tuple<std::iter_value_t<T1>>, boost::callable_traits::args_t<T2>>)
auto recursive_count_if(const T1& input, const T2 predicate)
{
return std::count_if(input.begin(), input.end(), predicate);
}

//  transform_reduce version
template<class T1, class T2> requires (is_iterable<T1> && !std::same_as<std::tuple<std::iter_value_t<T1>>, boost::callable_traits::args_t<T2>>)
auto recursive_count_if(const T1& input, const T2 predicate)
{
return std::transform_reduce(std::begin(input), std::end(input), std::size_t{}, std::plus<std::size_t>(), (predicate)(auto& element) {
return recursive_count_if(element, predicate);
});
}


The used is_iterable concept:

template<typename T>
concept is_iterable = requires(T x)
{
*std::begin(x);
std::end(x);
};


The constraints of usage

Because the type in the input lambda function plays the role of termination condition, you can not use auto keyword as generic lambdas here. If the lambda function like ()(auto element) { } is passed in, compiling errors will pop up. If you want to use generic lambdas, maybe you can choose the previous version recursive_count_if function due to the termination condition is separated.

All suggestions are welcome.

The summary information:

## Design that hides cache as an implementation detail

So first as a small point – finalize is depreciated. Don’t use it. You need to rely on calling contexts to handle closing the object. Use try-with-resources where you can and maybe use reference counting to know when to de-allocate the underlying object.

Beyond that, what want sounds most like object pooling. You can take inspiration from libraries like Jedis where there is an interface that represents all the operations you can perform and an object pool you can ask to borrow something that implements that interface from. You then either have your operations interface implement closable or make some sub interface that does, and calling .close() on that returned object returns it to the pool.

In that example everything is using Apache Commons Pool which, while I have no experience using except as a consumer, seems to be in the right direction.

The same general technique is used by any sort of “resource pooling” object like HikariCP which pools database connections or java’s Executors which pool access to threads.

To make everything work properly across multiple threads, I do suggest using a library like Commons Pool, but we can show the general pattern without it.

First, segregate out the operations of Heavy

public interface Heavy extends Closeable {
}


If you are on the newest Java this might be a good place to use sealed interfaces.

Next, make your actual implementation that handles the native resource.

final class HeavyNative implements Heavy {
private final Pointer pointer;

HeavyNative(String name) {
this.pointer = ...???...;
}

@Override
public int add(int x, int y) {
// oogabooga
}

@Override
public void close() {
pointer.free();
}
}


Depending on how you are structuring things, you might see some benefit in making the actual implementations here package-private, which is what I am doing.

Then you can make your object that lets you borrow a Heavy. I am going to hand-wave this a bit and use synchronized for everything, but do look into Apache Commons Pool and similar libraries. That being said, if you are reluctant to use dependencies at all, this will (probably) work.

public final class HeavyFactory {
// You could also wrap this logic into HeavyNative or make an entirely separate class
// or make it not atomic since that doesn't super matter in an entirely synchronized
// context.
private static record RefCountedHeavy(Heavy heavy, AtomicInteger rc);

private Map<String, RefCountedHeavy> givenOut = new HashMap<>();

public synchronized Heavy getHeavy(String name) {
if (givenOut.contains(name)) {
final var refCountedHeavy = givenOut.get(name);
return new BorrowedHeavy(name, refCountedHeavy.heavy(), this);
}
else {
final var heavy = new HeavyNative(name);
this.givenOut.put(name, new RefCountedHeavy(heavy, new AtomicInteger(1)));
return new BorrowedHeavy(name, heavy, this);
}
}

synchronized void returnHeavy(BorrowedHeavy heavy) {
final var refCountedHeavy = givenOut.get(heavy.name);
if (rc == 0) {
// no one is using it
refCountedHeavy.heavy().close();
givenOut.remove(heavy.name);
}
}

}


So you can get a Heavy from this, and if you know you have a Heavy that is borrowed you can return it. Then for BorrowedHeavy:

 // This could be a static class in the factory if you wanted
final class BorrowedHeavy implements Heavy {
// Or whatever other book keeping you want accessible to handle returns
// you can make whatever the "key" is part of the interface or do some other
// method of book keeping if you want.
final String name;
private final Heavy heavy;
private final HeavyFactory maker;

BorrowedHeavy(String name, Heavy heavy, HeavyFactory maker) {
this.name = name;
this.heavy = heavy;
this.maker = maker;
}

// delegate all functionality
@Override
public int add(int x, int y) {
}

@Override
public void close() {
this.maker.returnHeavy(this);
}
}


Then, when all is said and done, you just need to maintain a reference to a single HeavyFactory everywhere.

In fact, you could even make HeavyFactory package private and make a singleton instance on the Heavy interface.

public interface Heavy extends Closeable {
private static HeavyFactory factory = new HeavyFactory();

static Heavy forName(String name) {
return factory.getHeavy(name);
}

}


At which point the public interface into your code is just that single method and you are free to fiddle about with the specifics of pooling however you want to.

try (final var heavy = Heavy.forName("abc")) {
}


Does that make sense? I know the code got kinda messy with BorrowedHeavy and HeavyFactory so I can clean up or clarify if needed, but to summarize the general points:

• What data structure to use? Probably hash map unless you want to include libraries at which point just use libraries made for object pooling.
• How do you get wrapper objects to communicate back? Give them a reference to the factory when they are made and communicate at close() time.

## c – Unival Tree Implementation

I have written some code to solve the following interview question. Please advise how it can be improved. Thanks in advance.

A unival tree (which stands for “universal value”) is a tree where all nodes under it have the same value. Given the root to a binary tree, count the number of unival subtrees.
For example, the following tree has 5 unival subtrees:

Implementation:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct stTree
{
struct stTree * left;
struct stTree * right;
int value;
}

stTree;

stTree* createNode(int value)
{
stTree *node = malloc(sizeof *node);
node->left = NULL;
node->right = NULL;
node->value = value;

return node;
}

bool isTreeUniv(stTree *node)
{
bool flag = true;

if (!node)
return false;

if (node->right && node->right->value != node->value)
{
flag = false;
}

if (node->left && node->left->value != node->value)
{
flag = false;
}

return flag;
}

stTree* insertRight(stTree *currNode, int value)
{
stTree *node = malloc(sizeof *node);

currNode->right = node;
node->left = NULL;
node->right = NULL;
node->value = value;
return node;
}

stTree* insertLeft(stTree *currNode, int value)
{
stTree *node = malloc(sizeof *node);

currNode->left = node;
node->left = NULL;
node->right = NULL;
node->value = value;
return node;
}

unsigned int uTreeCount = 0;
void countUnivSubT(stTree *Node)
{
if (isTreeUniv(Node))
uTreeCount++;

if (Node->left)
countUnivSubT(Node->left);

if (Node->right)
countUnivSubT(Node->right);

}

int main(void)
{
//build a tree
stTree *rootNode = createNode(0);
insertLeft(rootNode, 1);
insertRight(rootNode, 0);

insertLeft(rootNode->right, 1);
insertRight(rootNode->right, 0);

insertLeft(rootNode->right->left, 1);
insertRight(rootNode->right->left, 1);

countUnivSubT(rootNode);
printf("total universal subree: %un", uTreeCount);

}


## recursion – A recursive_count_if Function with Specified value_type for Various Type Arbitrary Nested Iterable Implementation in C++

This is a follow-up question for A recursive_count_if Function For Various Type Arbitrary Nested Iterable Implementation in C++. Thanks to Quuxplusone’s answer and G. Sliepen’s comments. Based on the mentioned std::vector<std::vector<std::string>> case, it indicates a problem about the process of unwrapping nested iterable structure. In order to make recursive_count_if function be more generic, I am trying to implement another version of recursive_count_if template function with checking container’s value_type matches specified type. The process of unwrapping nested iterable structure would keep running until the base type in container is as same as the given type T1.

//  recursive_count_if implementation
template<class T1, class T2, class T3> requires (is_iterable<T2> && std::same_as<std::iter_value_t<T2>, T1>)
auto recursive_count_if(const T2& input, const T3 predicate)
{
return std::count_if(input.begin(), input.end(), predicate);
}

//  transform_reduce version
template<class T1, class T2, class T3> requires (is_iterable<T2> && !std::same_as<std::iter_value_t<T2>, T1>)
auto recursive_count_if(const T2& input, const T3 predicate)
{
return std::transform_reduce(std::begin(input), std::end(input), std::size_t{}, std::plus<std::size_t>(), (predicate)(auto& element) {
return recursive_count_if<T1>(element, predicate);
});
}


The test cases for this version recursive_count_if template function:

//  std::vector<std::vector<int>> case
std::vector<int> test_vector{ 1, 2, 3, 4, 4, 3, 7, 8, 9, 10 };
std::vector<decltype(test_vector)> test_vector2;
test_vector2.push_back(test_vector);
test_vector2.push_back(test_vector);
test_vector2.push_back(test_vector);

// use a lambda expression to count elements divisible by 3.
int num_items1 = recursive_count_if<int>(test_vector2, ()(int i) {return i % 3 == 0; });
std::cout << "#number divisible by three: " << num_items1 << 'n';

//  std::deque<std::deque<int>> case
std::deque<int> test_deque;
test_deque.push_back(1);
test_deque.push_back(2);
test_deque.push_back(3);

std::deque<decltype(test_deque)> test_deque2;
test_deque2.push_back(test_deque);
test_deque2.push_back(test_deque);
test_deque2.push_back(test_deque);

// use a lambda expression to count elements divisible by 3.
int num_items2 = recursive_count_if<int>(test_deque2, ()(int i) {return i % 3 == 0; });
std::cout << "#number divisible by three: " << num_items2 << 'n';

//  std::vector<std::vector<std::string>> case
std::vector<std::vector<std::string>> v = { {"hello"}, {"world"} };
auto size5 = ()(std::string s) { return s.size() == 5; };
auto n = recursive_count_if<std::string>(v, size5);
std::cout << "n:" << n << std::endl;


The output of std::vector<std::vector<std::string>> case is:

n:2


Besides the std::vector<std::vector<std::string>> case, you can also play this recursive_count_if template function like this:
(test_vector2 is from the above usage)

//  std::vector<std::vector<std::vector<int>>> case
std::vector<decltype(test_vector2)> test_vector3;
test_vector3.push_back(test_vector2);
test_vector3.push_back(test_vector2);
test_vector3.push_back(test_vector2);
std::cout << recursive_count_if<decltype(test_vector2)>(test_vector3,
(test_vector2)(auto& element)
{
return std::equal(element.begin(), element.end(), test_vector2.begin());
}) << std::endl;


All suggestions are welcome.

The summary information:

• Which question it is a follow-up to?

A recursive_count_if Function For Various Type Arbitrary Nested Iterable Implementation in C++

• What changes has been made in the code since last question?

The previous version recursive_count_if template function is hard to deal with std::vector<std::vector<std::string>> case. The experimental improved code has been proposed here.

• Why a new review is being asked for?

In order to perform container’s value_type matching structure, the std::same_as syntax and std::iter_value_t syntax are used here. The getting container’s value_type part is handled by std::iter_value_t and the type matching part is handled by std::same_as. I am not sure if this is a good implementation.

On the other hand, although the separated template parameter T1 plays the role of termination condition well, I am trying to deduce the type T1 form the given SFINAE-friendly lambda function (const T3 predicate here, assume that the given lambda function is SFINAE-friendly without something including auto syntax) so that making the following usage possible (just like the same usage in Quuxplusone’s answer ).

//  std::vector<std::vector<std::string>> case
std::vector<std::vector<std::string>> v = { {"hello"}, {"world"} };
auto size5 = ()(std::string s) { return s.size() == 5; };
auto n = recursive_count_if(v, size5);            //  the <std::string> is no needed to pass in again.
std::cout << "n:" << n << std::endl;


I’ve checked some discussions about getting the type of a lambda argument, including Can we get the type of a lambda argument?, Is it possible to retrieve the argument types from a (Functor member’s) function signature for use in a template?, Getting the type of lambda arguments and C++ template deduction from lambda. I think that I have no idea about how to deduce the type T1 automatically. Is it possible done with std::function like the experimental code as below?

template<class T1, class T2, class T3> requires (is_iterable<T1> && std::same_as<std::iter_value_t<T1>, T3>)
auto recursive_count_if(const T1& input, const std::function<T2(T3)> predicate)
{
//...
}


However, I think that maybe T3 is not the input type of the passed lambda function in the above structure based on some experiments. If I misunderstand something, please tell me. Moreover, please give me some hints or examples if there is any other better way.

If there is any further possible improvement, please let me know.

## consensus – Raft Implementation – Computer Science Stack Exchange

Thanks for contributing an answer to Computer Science Stack Exchange!

But avoid

• Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.

## python – increase efficiency of loops and element-wise operations in PyTorch implementation

For any input matrix W, I have the following implementation in PyTorch. I was wondering if the following can be improved in terms of efficiency,

P.S. Would current implementation break backpropagation?

import torch

W = torch.tensor(((0,1,0,0,0,0,0,0,0),
(1,0,1,0,0,1,0,0,0),
(0,1,0,3,0,0,0,0,0),
(0,0,3,0,1,0,0,0,0),
(0,0,0,1,0,1,1,0,0),
(0,1,0,0,1,0,0,0,0),
(0,0,0,0,1,0,0,1,0),
(0,0,0,0,0,0,1,0,1),
(0,0,0,0,0,0,0,1,0)))

n = len(W)
C = torch.empty(n, n)
I = torch.eye(n)
for i in range(n):
for j in range(n):
B = W.clone()
B(i, j) = 0
B(j, i) = 0

tmp = torch.inverse(n * I - B)

C(i, j) = tmp(i, j)


## Python Conway’s Game of Life Implementation

I am making Conway’s game of life in python, and I am a beginner. I decided to use 6 functions overall to implement it and here they are:

Function 1: create a blank grid
input: nothing
return: a blank grid

Function 2: print a given grid
input: a grid
return: nothing

input: a file name, a grid
return: nothing

Function 4: advance a grid one generation
input: a grid
return: a new grid advanced by one generation

Function 5: advance a cell one generation
input: a row, a column, a grid
return: whether the cell is alive or not (True or False)

Function 6: determine the number of living neighbors of a cell
input: a row, a column, a grid
return: the number of living neighbors of the cell

Function 5 and 6 are really just helpers to 4 because you need 6 for 5, and 5 for 4. I have done 1, 2, 3, 5, and 6, and I am working on 4 right now, but I get an error when I run my code in function 6.

living_cell = "O"

def create_blank_grid():
# # line = (dead_cell for i in range(59))
# line = ()
# for i in range(59):
#
# # grid = (("-") * 30 for i in range(60))
# line.append("n")
# # grid = (line for i in range(30))

line = ()
for i in range(59):
line.append("n")

grid = ()
for j in range(30):
grid.append(line(:))

# 11 31
# 11 32
# 12 31
# 12 33
# 13 32

return grid

# print(create_blank_grid())

def print_grid(grid):
for i in grid:
# print(len(i))
for j in i:
if j == "n":
print(" " * (69 - 59))
else:
print(j, end="")

return grid

# print_grid(create_blank_grid())

myFile = open(file_name, "r")
coordinates = ()
for line in myFile:
real_line = line.split()
row, col = real_line(0), real_line(1)
coordinates.append((row, col))
myFile.close()

# turn on certain cells here

for row, col in coordinates:
row, col = int(row), int(col)
# print(row, col)
grid(row)(col) = living_cell
# print_grid(grid)

for i in grid:
# print(len(i))
for j in i:
print(j, end="")
# return grid

# square.in just has coordinates (row, col) in str form like this:
# 11 31
# 11 32
# 12 31
# 12 32

def num_living_neighbors(row, col, grid):
# just to make sure
row = int(row)
col = int(col)

living_neighbors_count = 0

# if grid(row)(col + 1) == living_cell:
#     living_neighbors_count += 1

# if grid(row)(col - 1) == living_cell:
#     living_neighbors_count += 1

# if grid((row + 1) % len(grid))(col) == living_cell:
#     living_neighbors_count += 1

# if grid(row - 1)(col) == living_cell:
#     living_neighbors_count += 1

# if grid((row + 1) % len(grid))((col + 1) % len(grid)) == living_cell:
#     living_neighbors_count += 1

# if grid((row + 1) % len(grid))((col - 1) % len(grid)) == living_cell:
#     living_neighbors_count += 1

# if grid(row - 1)(col + 1) == living_cell:
#     living_neighbors_count += 1

# if grid(row - 1)(col - 1) == living_cell:
#     living_neighbors_count += 1

if (col + 1) < len(grid(row)) and grid(row)(col + 1) == living_cell:
living_neighbors_count += 1

if (col - 1) >= 0 and grid(row)(col - 1) == living_cell:
living_neighbors_count += 1

if (row + 1) < len(grid(row)) and grid(row + 1)(col) == living_cell:
living_neighbors_count += 1

if (row - 1) >= 0 and grid(row - 1)(col) == living_cell:
living_neighbors_count += 1

if (((col + 1) < len(grid(row))) and (row + 1) < len(grid(row))) and grid(row + 1)(col + 1) == living_cell:
living_neighbors_count += 1

if (((row + 1) < len(grid(row))) and (col - 1) >= 0) and grid(row + 1)(col - 1) == living_cell:
living_neighbors_count += 1

if (((row - 1) >= 0) and (col + 1) < len(grid(row))) and grid(row - 1)(col + 1) == living_cell:
living_neighbors_count += 1

if (((row - 1) >= 0) and (col - 1) >= 0) and grid(row - 1)(col - 1) == living_cell:
living_neighbors_count += 1

return living_neighbors_count

living = ()

# is alive, less than 2 alive neighbors
if grid(row)(col) == living_cell and num_living_neighbors(row, col, grid) < 2:
# return False

# is alive, 2 or 3 alive neighbors
if grid(row)(col) == living_cell and (
num_living_neighbors(row, col, grid) == 2 or num_living_neighbors(row, col, grid) == 3):
# return True
living.append((row, col))

# is alive, more than 4 alive neighbors
if grid(row)(col) == living_cell and num_living_neighbors(row, col, grid) > 4:
# return False

# is dead, has 3 alive neighbors
if grid(row)(col) == dead_cell and num_living_neighbors(row, col, grid) == 3:
# return True
living.append((row, col))

for i in grid:
for j in i:
if (i, j) in living:
print(living_cell)

for i in range(len(grid)):
for j in range(i):

# for i in range(len(grid)):
#     for j in range(len(grid(i))):
#         if adv_cell_one_gen(j, i, grid) == True:
#             grid(i)(j) = living_cell
#         else:

return grid



When I run this I get this error:

Traceback (most recent call last):
File "C:/Users/Krish/python-masterclass/current-python-masterclass-remaster/HelloWorld/conway's game of life.py", line 231, in <module>