kartikkukreja

struct SegmentTreeNode {
  int prefixMaxSum, suffixMaxSum, maxSum, sum;
  
  void assignLeaf(int value) {
    prefixMaxSum = suffixMaxSum = maxSum = sum = value;
  }
  
  void merge(SegmentTreeNode& left, SegmentTreeNode& right) {
    sum = left.sum + right.sum;
    prefixMaxSum = max(left.prefixMaxSum, left.sum + right.prefixMaxSum);

kartikkukreja

// T is the type of input array elements
// V is the type of required aggregate statistic
template<class T, class V>
class SegmentTree {
  SegmentTreeNode* nodes;
  int N;

public:
  SegmentTree(T arr[], int N) {
    this->N = N;

kartikkukreja

// We want to update the value associated with index in the input array 
void update(int index, T value) {
  update(1, 0, N-1, index, value);
}

// nodes[stIndex] is responsible for segment [lo, hi]
void update(int stIndex, int lo, int hi, int index, T value) {
  if (lo == hi) {
    nodes[stIndex].assignLeaf(value);
    return;

kartikkukreja

// V is the type of the required aggregate statistic
V getValue(int lo, int hi) {
  SegmentTreeNode result = getValue(1, 0, N-1, lo, hi);
  return result.getValue();
}

// nodes[stIndex] is responsible for the segment [left, right]
// and we want to query for the segment [lo, hi]
SegmentTreeNode getValue(int stIndex, int left, int right, int lo, int hi) {
  if (left == lo && right == hi)

kartikkukreja

struct SegmentTreeNode {
  // variables to store aggregate statistics and
  // any other information required to merge these
  // aggregate statistics to form parent nodes
  
  void assignLeaf(T value) {
    // T is the type of input array element
    // Given the value of an input array element,
    // build aggregate statistics for this leaf node
  }

kartikkukreja

void buildTree(T arr[], int stIndex, int lo, int hi) {
  if (lo == hi) {
    nodes[stIndex].assignLeaf(arr[lo]);
    return;
  }
  
  int left = 2 * stIndex, right = left + 1, mid = (lo + hi) / 2;
  buildTree(arr, left, lo, mid);
  buildTree(arr, right, mid + 1, hi);
  nodes[stIndex].merge(nodes[left], nodes[right]);

kartikkukreja

int getSegmentTreeSize(int N) {
  int size = 1;
  for (; size < N; size <<= 1);
  return size << 1;
}

kartikkukreja

void print_sequence(int multiple, int decrement, int N) {
  if (2 * multiple - decrement > N) {
    printf("%d ", multiple - decrement);
    return;
  }
  print_sequence(2 * multiple, decrement + multiple, N);
  print_sequence(2 * multiple, decrement, N);
}

void print_sequence(int N) {

kartikkukreja

bool order(int x, int y) {
  int xr = x ^ y, lowest_diff_bit = xr&(-xr);
  return (x & lowest_diff_bit);
}

void print_sequence(int N) {
  int* A = new int[N];
  for (int i = 0; i < N; ++i)
    A[i] = i+1;
  	

kartikkukreja

void print_permutation(int lo, int hi) {
  if (lo > hi)
    return;
  int mid = (lo + hi) / 2;
  printf("%d ", mid);
  print_permutation(lo, mid-1);
  print_permutation(mid+1, hi);
}

void print_permutation(int N) {