## Design Excel Sum Formula

• Time:Constructor: O(\texttt{height} \cdot \texttt{width}), set(row: int, column: chr, val: int), get(row: int, column: chr): O(1), sum(row: int, column: chr, numbers: List[str]): O(|\texttt{numbers}|)
• Space:O(\texttt{height} \cdot \texttt{width})

## C++

struct Cell {
int val = 0;
unordered_map<int, int> posCount;  // {pos: count}
};

class Excel {
public:
Excel(int height, char width)
: width(width), sheet(height, vector<Cell>(width)) {}

void set(int row, char column, int val) {
getCell(row, column) = {val, {}};
}

int get(int row, char column) {
const Cell& cell = getCell(row, column);
if (cell.posCount.empty())
return cell.val;

int val = 0;
for (const auto& [pos, count] : cell.posCount)
val += get(pos / width + 1, pos % width + 'A') * count;
return val;
}

int sum(int row, char column, vector<string> numbers) {
getCell(row, column).posCount = parse(numbers);
return get(row, column);
}

private:
int width;
vector<vector<Cell>> sheet;

Cell& getCell(int row, char column) {
return sheet[row - 1][column - 'A'];
}

unordered_map<int, int> parse(const vector<string>& numbers) {
unordered_map<int, int> count;
for (const string& s : numbers) {
const auto [startRow, startCol, endRow, endCol] = parse(s);
for (int i = startRow - 1; i < endRow; ++i)
for (int j = startCol - 'A'; j < endCol - 'A' + 1; ++j)
++count[i * width + j];
}
return count;
}

tuple<int, char, int, char> parse(const string& s) {
if (s.find(':') == string::npos)
return {stoi(s.substr(1)), s[0], stoi(s.substr(1)), s[0]};

const int colonIndex = s.find_first_of(':');
const string& l = s.substr(0, colonIndex);
const string& r = s.substr(colonIndex + 1);
return {stoi(l.substr(1)), l[0], stoi(r.substr(1)), r[0]};
}
};


## JAVA

class Cell {
public int val = 0;
public Map<Integer, Integer> posCount = new HashMap<>(); // {pos, count}
public Cell(int val, Map<Integer, Integer> posCount) {
this.val = val;
this.posCount = posCount;
}
}

class Excel {
public Excel(int height, char width) {
this.width = width;
this.sheet = new Cell[height][width];

for (int i = 0; i < height; ++i)
for (int j = 0; j < width; ++j)
sheet[i][j] = new Cell(0, null);
}

public void set(int row, char column, int val) {
sheet[row - 1][column - 'A'] = new Cell(val, null);
}

public int get(int row, char column) {
Cell cell = sheet[row - 1][column - 'A'];
if (cell.posCount == null)
return cell.val;

int val = 0;
for (var entry : cell.posCount.entrySet()) {
final int pos = entry.getKey();
final int count = entry.getValue();
val += get(pos / width + 1, (char) ((pos % width) + 'A')) * count;
}
return val;
}

public int sum(int row, char column, String[] numbers) {
sheet[row - 1][column - 'A'].posCount = parse(numbers);
return get(row, column);
}

private int width;
private Cell[][] sheet;

private Map<Integer, Integer> parse(String[] numbers) {
Map<Integer, Integer> count = new HashMap<>();

for (final String s : numbers) {
var tokens = parse(s);
final int startRow = Integer.parseInt(tokens.getKey().substring(1));
final char startCol = tokens.getKey().charAt(0);
final int endRow = Integer.parseInt(tokens.getValue().substring(1));
final char endCol = tokens.getValue().charAt(0);
for (int i = startRow - 1; i < endRow; ++i)
for (int j = startCol - 'A'; j < endCol - 'A' + 1; ++j)
count.merge(i * width + j, 1, Integer::sum);
}

return count;
}

private Pair<String, String> parse(final String s) {
if (!s.contains(":"))
return new Pair<>(s, s);

String[] tokens = s.split(":");
return new Pair<>(tokens[0], tokens[1]);
}
}


## Python

class Cell:
def __init__(self, val: int, posCount: Optional[Dict[Tuple[int, int], int]]):
self.val = val
self.posCount = posCount  # {pos, count}

class Excel:
def __init__(self, height: int, width: str):
self.sheet = [[Cell(0, None) for i in range(height)]
for _ in range(ord(width) - ord('A') + 1)]

def set(self, row: int, column: str, val: int) -> None:
self.sheet[row - 1][ord(column) - ord('A')] = Cell(val, None)

def get(self, row: int, column: str) -> int:
cell = self.sheet[row - 1][ord(column) - ord('A')]
if cell.posCount:
return sum(self.get(*pos) * freq for pos, freq in cell.posCount.items())
return cell.val

def sum(self, row: int, column: str, numbers: List[str]) -> int:
self.sheet[row - 1][ord(column) - ord('A')].posCount = self._parse(numbers)
return self.get(row, column)

def _parse(self, numbers: List[str]):
count = Counter()
for n in numbers:
s, e = n.split(':')[0], n.split(':')[1] if ':' in n else n
for i in range(int(s[1:]), int(e[1:]) + 1):
for j in range(ord(s[0]) - ord('A'), ord(e[0]) - ord('A') + 1):
count[(i, chr(j + ord('A')))] += 1
return count