triunghi

Intuiție / reformulare

Pentru fiecare zonă vreau suma ei, iar la final maximul. Suma „cu mâna”, celulă cu celulă, e corectă (pe exemplu dă $59$), dar o zonă are până la $\sim |k|^2 / 2$ celule. Cu $Q = 100\,000$ interogări și $|k|$ până la $1\,000$, asta înseamnă până la $\sim 10^{11}$ operații — imposibil în timp. Am nevoie de un mod de a calcula suma unui triunghi în timp constant.

Truc-ul e să nu privesc triunghiul ca pe o grămadă de celule, ci pe rânduri: fiecare rând al lui e un segment continuu, deci suma rândului e deja o diferență de prefixe pe rând. Când adun toate rândurile, termenii se regrupează în două bucăți pe care le pot pre-tabela: o latură verticală (o coloană) și o margine oblică (o anti-diagonală).