5
\$\begingroup\$

I have solved a typical segment-tree problem, which lets you update one single value to another in the array, or to get, from i to j, the sum of each element multiplied by an integer B to the power of j-i-k, being i <= k <= j the index of the new element, k=0 i and k=j-i being j, all of that modulo P. (\$\sum_{k=0}^{j-i} f_{j-k} B^{k} \pmod{P}\$).

E.g.:

arr[5] = {1,3,2,5,8};
int B = 4, P = 10;

int resFrom2to4 = (2*4^2 + 5*4^1 + 8*4^0) % 10;

The focus is not on the solving but in my code, because I want to make it more readable and avoid bad methods to improve future projects. Variable names I already know they are horrible but this is due to me always using the same letters for each thing (N -> size, Q -> queries, K -> constant...).

Also ignore things such as #define int long long and using namespace std, because I only use them for competitions, but if I am doing something serious I know they are bad and can lead to problems.

Also note that I am using C++11.

#include <iostream>
#include <vector>
#include <string>
#include <cassert>

using namespace std;

#define int long long

int pot(int a, int b, int MOD){
  if (b == 0) return 1;

  int x = pot(a, b/2, MOD) % MOD;

  if (b % 2 == 0){
    return x * x % MOD;
  } else {
    return x*x % MOD * a % MOD;
  }
}

inline int IZ(int i){ // izquierda (es) = right (en)
  return 2*i; 
}
inline int DC(int i){ // derecha (es) = left (en)
  return 2*i + 1;
}

struct segment_tree{
  int B, P, N;
  vector<int> ST;

  segment_tree(int b, int p, int n) : B(b), P(p), N(n), ST(n * 4, 0) {};

  int get(int a, int b){
    return get(1, 0, N-1, a-1, b-1);
  }

  int get(int node, int l, int r, int a, int b){
    assert(a <= r && b >= l);

    if (a <= l && r <= b){
      return ST[node];
    }

    int m = (l+r) / 2;
    int total = 0;
    int sizR = min(b,r) - m;

    if (a <= m){
      total += get(IZ(node), l, m, a, b) * pot(B, max(sizR, 0LL), P) % P;
    }
    if (sizR > 0){
      total += get(DC(node), m+1, r, a, b) % P;
    }

    return total % P;
  }

  void put(int pos, int val){
    put(1, 0, N-1, pos-1, val);
  }

  void put(int node, int l, int r, int pos, int val){
    assert(l <= pos && pos <= r);

    if (r == l){
      ST[node] = val % P;
      return;
    }

    int m = (l+r) / 2;
    if (pos <= m){
      put(IZ(node), l, m, pos, val);
    } else {
      put(DC(node), m+1, r, pos, val);
    }

    ST[node] = ((ST[IZ(node)] * pot(B, max(r-m, 0LL), P)) % P + ST[DC(node)]) % P;
  }
};

bool solve(){
  int B, P, N; cin >> B >> P >> N;
  if (!cin) return false;

  segment_tree ST(B, P, N);

  string Q; cin >> Q;
  while(Q != "FIN"){
    if (Q == "E"){
      int p, v; cin >> p >> v;
      ST.put(p, v);
    } else if (Q == "H"){
      int a, b; cin >> a >> b;
      cout << ST.get(a, b) << '\n';
    }

    cin >> Q;
  }

  cout << "---\n";
  return true;
}

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);

  while(solve());
  return 0;
}
\$\endgroup\$

1 Answer 1

Reset to default
8
\$\begingroup\$

Fix the things you already know need fixing

The focus is not on the solving but in my code, because I want to make it more readable and avoid bad methods to improve future projects.

That's great, readable and future-proof code is always good to aim for. But now I'm surprised:

Variable names I already know they are horrible

So why not fix it? Don't accept your own excuses, and go change N to size, Q to queries, and so on.

Also ignore things such as #define int long long and using namespace std, because I only use them for competitions

Nope, don't ignore that! Also, why do you use those things for competitions? They don't make the code any faster! The competitions are about implementing the right algorithm and making the program run fast, not about making the source code as small as possible.

Notice how your #define also required you to use a hack to even be able to write a valid main() function. There are other ways to solve this issue. You could for example create a type alias:

using integer = long long;

integer pot(integer a, integer b, integer MOD) {
    …
}

Also, using namespace std doesn't save typing as much as you think, and that's before even taking into account that most code editors support tab completion.

Also note that I am using C++11.

Why use such an old version of C++? Newer versions have features that make it easier to write code, and in some cases is even faster.

Rename everything

A good exercise is to go and find every function, variable and type name, and change it so you know what it means without having to look at comments or at other parts of the code. Names don't have to be very long, they should be concise.

Also make sure you are consistent: why is pot() in lower case, but IZ() upper case? Why is pot() an (abbreviation for an) English word, but IZ() Spanish?

I also recommend you use lower case for variable names and functions, but make types (like classes and structs) start with a capital.

Make a more generic class SegmentTree

Your struct segment_tree probably does whatever you needed to solve the code challenge, but it looks very messy: apart from the names of things, everything is public, it's hardcoded to use "int"s, and I have no idea why get() returns a single integer, when normally you'd expect to either get a set of intervals that contain a given point, or a perhaps a set of intervals that completely or partially overlap a given range.

It might be nice to define types or type aliases for node indices, points and segments. I would expect it to look something like:

template<typename T>
class SegmentTree {
    …
public:
    struct Segment {
        T start;
        T end;
    };

    void add(Segment segment);
    std::vector<Segment> get(T point);
    …
};

And of course, the challenge is in getting the same performance and functionality out of it that you need for solving code challenges. There is no reason you can't have both a nice interface and performant code!

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.