sp_matrice.xhtml

        
            
1
            <?xml version="1.0" encoding="UTF-8"?>
        
            
2
            <!DOCTYPE html>
        
            
3
            <html xmlns="http://www.w3.org/1999/xhtml">
        
            
4
                <head>
        
            
5
                    <meta charset="utf-8"/>
        
            
6
                    <title>Clasele vector&lt;&gt;. Sume parțiale pe matrice.</title>
        
            
7
                    <link rel="stylesheet" href="style.css"/>
        
            
8
                </head>
        
            
9
                <body>
        
            
10
                    <h1>Clasele <code>vector&lt;&gt;</code>. Sume parțiale pe matrice.</h1>
        
            
11
                    <section>
        
            
12
                        <h2><code>vector&lt;&gt;</code></h2>
        
            
13
                        <aside class="definition">
        
            
14
                            <p>
        
            
15
                                <b>Context:</b>
        
            
16
                                <i>Clasa</i> este un tip de date compus care definește
        
            
17
                                operații definite de autorul tipului. Unele operații se
        
            
18
                                folosesc prin operatori și altele sunt funcții interioare
        
            
19
                                clasei (numite și <i>metode</i>) care se accesează cu
        
            
20
                                punct și primesc parametri ca o funcție obișnuită.
        
            
21
                                Momentan nu ne interesează definirea claselor. Clasele
        
            
22
                                pot avea derivate, care moștenesc caracteristicile bazei
        
            
23
                                și le extind, și pot fi șabloane, adică să permită
        
            
24
                                utilizatorului să specifice anumite părți din clasă
        
            
25
                                (tipurile de date din care se compune).
        
            
26
                            </p>
        
            
27
                            <p>
        
            
28
                                Instanțele unei clase se numesc <i>obiecte</i>. Câteva
        
            
29
                                clase pe care poate le știți deja: <code>istream</code>
        
            
30
                                (<code>cin</code> e o instanță a acestei clase),
        
            
31
                                <code>ifstream</code> (care e derivată din istream),
        
            
32
                                <code>string</code>.
        
            
33
                            </p>
        
            
34
                            <p>
        
            
35
                                În C++, clasa este sinonimă cu structura, dar acest
        
            
36
                                lucru nu este valabil pentru toate limbajele de programare
        
            
37
                                care oferă ambele opțiuni.
        
            
38
                            </p>
        
            
39
                            <p>
        
            
40
                                Când se creează un obiect, putem (uneori trebuie) să-i dăm
        
            
41
                                parametri, care vor fi trimiși funcției-constructor.
        
            
42
                                Binecunoscutul exemplu nu de fapt nimic altceva decât o
        
            
43
                                declarare de obiect cu parametru:
        
            
44
                            </p>
        
            
45
                            <pre><code>ifstream fin("numele.in");
        
            
46
            ofstream fout("numele.out");</code></pre>
        
            
47
                        </aside>
        
            
48
                        <p>
        
            
49
                            Până acum cunoașteți tipurile tradiționale de tablou,
        
            
50
                            care se declară cu sintaxa <code>TipDeBază nume[dimensiune]</code>.
        
            
51
                            Ele funcționează, dar sunt moștenite din limbajul C (1972).
        
            
52
                            Au deci câteva neajunsuri:
        
            
53
                        </p>
        
            
54
                        <ul>
        
            
55
                            <li>
        
            
56
                                nu își memorează dimensiunea, de aceea trebuie să
        
            
57
                                o memorăm separat și să ne amintim pentru fiecare
        
            
58
                                dimensiune care vector o folosește;
        
            
59
                            </li>
        
            
60
                            <li>
        
            
61
                                când sunt trimise în funcții, devin un simplu pointer,
        
            
62
                                și trebuie să fim atenți să nu facem operații fără sens
        
            
63
                                cu acel pointer (se fac foarte ușor);
        
            
64
                            </li>
        
            
65
                            <li>
        
            
66
                                nu pot fi redimensionați (fără alocare dinamică);
        
            
67
                            </li>
        
            
68
                            <li>
        
            
69
                                de fapt, conform standardului, dimensiunea trebuie să
        
            
70
                                fie o constantă determinată la compilare (însă GCC
        
            
71
                                permite și o dimensiune variabilă).
        
            
72
                            </li>
        
            
73
                        </ul>
        
            
74
                        <p>
        
            
75
                            În C++, spre deosebire de C, biblioteca standard ne pune la
        
            
76
                            dispoziție o alternativă, șablonul (template-ul) de tipuri
        
            
77
                            (clase) numit <code>vector</code>. Spre deosebire de tablourile
        
            
78
                            tradiționale:
        
            
79
                        </p>
        
            
80
                        <ul>
        
            
81
                            <li>
        
            
82
                                au dimensiune, care poate fi accesată folosind funcția
        
            
83
                                internă <code>size</code>;
        
            
84
                            </li>
        
            
85
                            <li>
        
            
86
                                această dimensiune se poate schimba oricând;
        
            
87
                            </li>
        
            
88
                            <li>
        
            
89
                                nu se transformă în pointer;
        
            
90
                            </li>
        
            
91
                            <li>
        
            
92
                                îi putem returna din funcții;
        
            
93
                            </li>
        
            
94
                            <li>
        
            
95
                                conținutul nu se alocă pe stivă, deci putem avea tablouri
        
            
96
                                oricât de mari dorim fără a le aloca global sau dinamic.
        
            
97
                            </li>
        
            
98
                        </ul>
        
            
99
                        <p>
        
            
100
                            <code>vector</code> este în antetul
        
            
101
                            <code>&lt;vector&gt;</code> și în spațiul de nume
        
            
102
                            <code>std</code> (dacă avem <code>using namespace std;</code>
        
            
103
                            nu trebuie să scriem asta).
        
            
104
                        </p>
        
            
105
                        <h3>Declararea vectorilor</h3>
        
            
106
                        <div class="gallery">
        
            
107
                            <figure>
        
            
108
                                <pre><code>vector&lt;<b>int</b>&gt; name;</code></pre>
        
            
109
                                <figcaption>Un vector gol care memorează valori de tipul <code>int</code></figcaption>
        
            
110
                            </figure>
        
            
111
                            <figure>
        
            
112
                                <pre><code><b>int</b> N;
        
            
113
            cin >> N;
        
            
114
            struct Structure {
        
            
115
                <b>int</b> a, b;
        
            
116
            }
        
            
117
            vector&lt;Structure&gt; p(N);</code></pre>
        
            
118
                                <figcaption>
        
            
119
                                    Un vector <code>p</code> care memorează valori de tipul
        
            
120
                                    <code>Structure</code>. Inițial are <code>N</code>
        
            
121
                                    elemente, care sunt inițializate cu 0.
        
            
122
                                </figcaption>
        
            
123
                            </figure>
        
            
124
                            <figure>
        
            
125
                                <pre><code>vector&lt;<b>short int</b>&gt; alphabet(26, -1);</code></pre>
        
            
126
                                <figcaption>
        
            
127
                                    Un vector care memorează inițial 26 de
        
            
128
                                    <code>short int</code>, având valoarea inițială
        
            
129
                                    de -1.
        
            
130
                                </figcaption>
        
            
131
                            </figure>
        
            
132
                            <figure>
        
            
133
                                <pre><code>vector&lt;<b>int</b>&gt; x = y;</code></pre>
        
            
134
                                <figcaption>
        
            
135
                                    Vectorul x este o copie a vectorului y.
        
            
136
                                </figcaption>
        
            
137
                            </figure>
        
            
138
                            <figure>
        
            
139
                                <pre><code>vector&lt;vector&lt;<b>int</b>&gt;&gt; x(N, vector&lt;<b>int</b>&gt;(M));</code></pre>
        
            
140
                                <figcaption>
        
            
141
                                    Un vector de vectori e o matrice. Transmitem cu ce
        
            
142
                                    parametri va fi inițializat fiecare element.
        
            
143
                                </figcaption>
        
            
144
                            </figure>
        
            
145
                        </div>
        
            
146
                        <h3>Operații de bază</h3>
        
            
147
                        <div class="gallery">
        
            
148
                            <figure>
        
            
149
                                <pre><code>vector&lt;<b>int</b>&gt; a(5);</code></pre>
        
            
150
                                <figcaption>
        
            
151
                                    Se declară acest vector.
        
            
152
                                </figcaption>
        
            
153
                            </figure>
        
            
154
                            <figure>
        
            
155
                                <pre><code>a[0]</code></pre>
        
            
156
                                <figcaption>
        
            
157
                                    Accesează elementul 0 din vector.
        
            
158
                                </figcaption>
        
            
159
                            </figure>
        
            
160
                            <figure>
        
            
161
                                <pre><code>a[1] = 67</code></pre>
        
            
162
                                <figcaption>
        
            
163
                                    Atribuirea se face în modul firesc.
        
            
164
                                </figcaption>
        
            
165
                            </figure>
        
            
166
                            <figure>
        
            
167
                                <pre><code>a.size()</code></pre>
        
            
168
                                <figcaption>
        
            
169
                                    Returnează dimensiunea vectorului, adică 5.
        
            
170
                                </figcaption>
        
            
171
                            </figure>
        
            
172
                            <figure>
        
            
173
                                <pre><code>a.capacity()</code></pre>
        
            
174
                                <figcaption>
        
            
175
                                    Returnează numărul de elemente disponibile pentru
        
            
176
                                    când se lărgește vectorul; dacă vectorul crește peste
        
            
177
                                    acest număr de elemente, se va realoca.
        
            
178
                                </figcaption>
        
            
179
                            </figure>
        
            
180
                        </div>
        
            
181
                        <h3>Operații care schimbă dimensiunea</h3>
        
            
182
                        <div class="gallery">
        
            
183
                            <figure>
        
            
184
                                <pre><code>a.resize(9)</code></pre>
        
            
185
                                <figcaption>
        
            
186
                                    Vectorul are acum 9 elemente în loc de 5. Cele
        
            
187
                                    noi sunt 0.
        
            
188
                                </figcaption>
        
            
189
                            </figure>
        
            
190
                            <figure>
        
            
191
                                <pre><code>a.resize(1)</code></pre>
        
            
192
                                <figcaption>
        
            
193
                                    Vectorul are acum un singur element, adică primul.
        
            
194
                                    Elementele în afară de acesta se pierd.
        
            
195
                                </figcaption>
        
            
196
                            </figure>
        
            
197
                            <figure>
        
            
198
                                <pre><code>a.reserve(32)</code></pre>
        
            
199
                                <figcaption>
        
            
200
                                    Vectorul se va realoca pentru a putea aduna 32 de
        
            
201
                                    elemente fără alte realocări. Util când putem afla
        
            
202
                                    o dimensiune orientativă (dacă nu chiar pe cea
        
            
203
                                    finală).
        
            
204
                                </figcaption>
        
            
205
                            </figure>
        
            
206
                            <figure>
        
            
207
                                <pre><code>a.push_back(8)</code></pre>
        
            
208
                                <figcaption>
        
            
209
                                    Adaugă un element la capăt. Vectorul are acum două
        
            
210
                                    elemente: 0 și 8.
        
            
211
                                </figcaption>
        
            
212
                            </figure>
        
            
213
                            <figure>
        
            
214
                                <pre><code>a.pop_back()</code></pre>
        
            
215
                                <figcaption>
        
            
216
                                    Vectorul pierde ultimul element.
        
            
217
                                </figcaption>
        
            
218
                            </figure>
        
            
219
                        </div>
        
            
220
                        <h3>Iteratori</h3>
        
            
221
                        <p>
        
            
222
                            Iteratorul este un obiect care indică o poziție din vector.
        
            
223
                            Este de tipul <code>vector&lt;TipDeBază&gt;::iterator</code>;
        
            
224
                            putem scrie <code><b>auto</b></code> pentru a nu folosi tot
        
            
225
                            numele.
        
            
226
                        </p>
        
            
227
                        <div class="gallery">
        
            
228
                            <figure>
        
            
229
                                <pre><code>a.begin()</code></pre>
        
            
230
                                <figcaption>
        
            
231
                                    Iterator pentru primul element din vector (0).
        
            
232
                                </figcaption>
        
            
233
                            </figure>
        
            
234
                            <figure>
        
            
235
                                <pre><code>a.end()</code></pre>
        
            
236
                                <figcaption>
        
            
237
                                    Iterator care se află după sfârșitul vectorului,
        
            
238
                                    este folosit ca un indicator că parcurgerea trebuie
        
            
239
                                    să se sfârșească.
        
            
240
                                </figcaption>
        
            
241
                            </figure>
        
            
242
                            <figure>
        
            
243
                                <pre><code>a.begin() + 1</code></pre>
        
            
244
                                <figcaption>
        
            
245
                                    Adunând iteratorul cu un număr putem obține un iterator
        
            
246
                                    pentru alt indice, în acest caz pentru elementul 1.
        
            
247
                                </figcaption>
        
            
248
                            </figure>
        
            
249
                            <figure>
        
            
250
                                <pre><code>a.end() - a.begin()</code></pre>
        
            
251
                                <figcaption>
        
            
252
                                    Putem și scădea iteratori și rezultatul este un număr
        
            
253
                                    întreg. Cu ce este egal rezultatul acestei expresii?
        
            
254
                                </figcaption>
        
            
255
                            </figure>
        
            
256
                            <figure>
        
            
257
                                <pre><code>++a</code></pre>
        
            
258
                                <figcaption>
        
            
259
                                    Mută iteratorul cu o poziție înainte.
        
            
260
                                </figcaption>
        
            
261
                            </figure>
        
            
262
                        </div>
        
            
263
                        <h3>Operații bazate pe iteratori</h3>
        
            
264
                        <div class="gallery">
        
            
265
                            <figure>
        
            
266
                                <pre><code>a.erase(a.begin())</code></pre>
        
            
267
                                <figcaption>
        
            
268
                                    Șterge primul element.
        
            
269
                                </figcaption>
        
            
270
                            </figure>
        
            
271
                            <figure>
        
            
272
                                <pre><code>a.insert(a.begin(), 5)</code></pre>
        
            
273
                                <figcaption>
        
            
274
                                    Inserează un element în vector.
        
            
275
                                </figcaption>
        
            
276
                            </figure>
        
            
277
                            <figure>
        
            
278
                                <pre><code>a.insert(a.begin(), b.begin(), b.end())</code></pre>
        
            
279
                                <figcaption>
        
            
280
                                    Copiază elementele dintre cei doi iteratori (aici cei
        
            
281
                                    din b) și le inserează la <code>a.begin()</code>.
        
            
282
                                </figcaption>
        
            
283
                            </figure>
        
            
284
                        </div>
        
            
285
                    </section>
        
            
286
                    <section>
        
            
287
                        <h2>Sume parțiale pe matrice</h2>
        
            
288
                        <p>
        
            
289
                            Definim de acum funcția <code>safe_get</code> care va
        
            
290
                            returna valoarea de la indicele dat dintr-un vector, dacă
        
            
291
                            indicele e valid; în caz contrar, va returna 0. O folosim
        
            
292
                            pentru a nu fi nevoiți să testăm mereu dacă urmează să
        
            
293
                            scădem din poziția -1.
        
            
294
                        </p>
        
            
295
            <pre><code><b>inline int</b> safe_get(vector&lt;<b>int</b>&gt; <b>const</b> &amp;a, <b>int const</b> i) {
        
            
296
                <b>if</b> (i &lt; 0 || a.size() &lt;= i) {
        
            
297
                    <b>return</b> 0;
        
            
298
                }
        
            
299
                <b>return</b> a[i];
        
            
300
            }</code></pre>
        
            
301
            <pre><code><b>inline int</b> safe_get(vector&lt;vector&lt;<b>int</b>&gt;&gt; <b>const</b> &amp;a, <b>int const</b> i, <b>int const</b> j) {
        
            
302
                <b>if</b> (i &lt; 0 || a.size() &lt;= i || j &lt; 0 || a[0].size() &lt;= j) {
        
            
303
                    <b>return</b> 0;
        
            
304
                }
        
            
305
                <b>return</b> a[i];
        
            
306
            }</code></pre>
        
            
307
                        <aside class="old-information">
        
            
308
                            <h3>Recapitularea sumelor parțiale</h3>
        
            
309
                            <p>
        
            
310
                                Pentru a obține sume parțiale pe un tablou liniar de
        
            
311
                                lungime N, calculăm suma pe fiecare prefix al tabloului,
        
            
312
                                adică suma elementelor de la 0 la i (inclusiv), pentru
        
            
313
                                fiecare i de la 0 la N-1.
        
            
314
                            </p>
        
            
315
                            <p>
        
            
316
                                După aceea, suma pe intervalul [l; r] va fi
        
            
317
                                <code>safe_get(r) - safe_get(l-1)</code>.
        
            
318
                            </p>
        
            
319
                        </aside>
        
            
320
                        <p>
        
            
321
                            Să luăm ca exemplu matricea <code>a</code>:
        
            
322
                        </p>
        
            
323
                        <table class="matrix" contenteditable="true">
        
            
324
                            <tr>
        
            
325
                                <td>12</td>
        
            
326
                                <td>0</td>
        
            
327
                                <td>-4</td>
        
            
328
                                <td>-8</td>
        
            
329
                                <td>3</td>
        
            
330
                            </tr>
        
            
331
                            <tr>
        
            
332
                                <td>-1</td>
        
            
333
                                <td>6</td>
        
            
334
                                <td>7</td>
        
            
335
                                <td>8</td>
        
            
336
                                <td>10</td>
        
            
337
                            </tr>
        
            
338
                            <tr>
        
            
339
                                <td>4</td>
        
            
340
                                <td>-3</td>
        
            
341
                                <td>9</td>
        
            
342
                                <td>1</td>
        
            
343
                                <td>4</td>
        
            
344
                            </tr>
        
            
345
                            <tr>
        
            
346
                                <td>11</td>
        
            
347
                                <td>7</td>
        
            
348
                                <td>9</td>
        
            
349
                                <td>8</td>
        
            
350
                                <td>12</td>
        
            
351
                            </tr>
        
            
352
                        </table>
        
            
353
                        <p>
        
            
354
                            Se calculează, pentru fiecare i și j, suma elementelor aflate
        
            
355
                            pe rânduri până la i și coloane până la j. Matricea
        
            
356
                            <code>ps</code>:
        
            
357
                        </p>
        
            
358
                        <table class="matrix" contenteditable="true">
        
            
359
                            <tr>
        
            
360
                                <td>12</td>
        
            
361
                                <td>12</td>
        
            
362
                                <td>8</td>
        
            
363
                                <td>0</td>
        
            
364
                                <td>3</td>
        
            
365
                            </tr>
        
            
366
                            <tr>
        
            
367
                                <td>11</td>
        
            
368
                                <td>17</td>
        
            
369
                                <td>20</td>
        
            
370
                                <td>20</td>
        
            
371
                                <td>27</td>
        
            
372
                            </tr>
        
            
373
                            <tr>
        
            
374
                                <td>15</td>
        
            
375
                                <td>18</td>
        
            
376
                                <td>30</td>
        
            
377
                                <td>31</td>
        
            
378
                                <td>42</td>
        
            
379
                            </tr>
        
            
380
                            <tr>
        
            
381
                                <td>26</td>
        
            
382
                                <td>36</td>
        
            
383
                                <td>57</td>
        
            
384
                                <td>66</td>
        
            
385
                                <td>89</td>
        
            
386
                            </tr>
        
            
387
                        </table>
        
            
388
                        <p>
        
            
389
                            Cum calculăm această sumă?
        
            
390
                        </p>
        
            
391
                        <table class="matrix" contenteditable="true">
        
            
392
                            <tr>
        
            
393
                                <td class="sel3"></td>
        
            
394
                                <td class="sel3"></td>
        
            
395
                                <td class="sel3"></td>
        
            
396
                                <td class="sel1"></td>
        
            
397
                                <td></td>
        
            
398
                            </tr>
        
            
399
                            <tr>
        
            
400
                                <td class="sel3"></td>
        
            
401
                                <td class="sel3"></td>
        
            
402
                                <td class="sel3">20</td>
        
            
403
                                <td class="sel1">20</td>
        
            
404
                                <td></td>
        
            
405
                            </tr>
        
            
406
                            <tr>
        
            
407
                                <td class="sel2"></td>
        
            
408
                                <td class="sel2"></td>
        
            
409
                                <td class="sel2">30</td>
        
            
410
                                <td class="sel4">31</td>
        
            
411
                                <td></td>
        
            
412
                            </tr>
        
            
413
                            <tr>
        
            
414
                                <td></td>
        
            
415
                                <td></td>
        
            
416
                                <td></td>
        
            
417
                                <td></td>
        
            
418
                                <td></td>
        
            
419
                            </tr>
        
            
420
                        </table>
        
            
421
                        <p>
        
            
422
                            Putem trece la suma pentru o anumită celulă folosind sumele
        
            
423
                            anterioare:
        
            
424
                        </p>
        
            
425
                        <ol>
        
            
426
                            <li>
        
            
427
                                se ia valoarea celulei actuale din matrice;
        
            
428
                            </li>
        
            
429
                            <li>
        
            
430
                                se iau toate celulele cu i mai mic și j mai mic sau egal
        
            
431
                                decât cea actuală (deci suma de deasupra celei actuale);
        
            
432
                            </li>
        
            
433
                            <li>
        
            
434
                                se iau toate celulele cu j mai mic și i mai mic sau egal
        
            
435
                                decât cea actuală (deci suma din stânga celei actuale);
        
            
436
                            </li>
        
            
437
                            <li>
        
            
438
                                acum toate celulele care ne interesează sunt selectate;
        
            
439
                                totuși, unele sunt selectate de două ori, mai precis cele
        
            
440
                                care îndeplinesc ambele condiții 2. și 3.; trebuie, așadar,
        
            
441
                                scăzute acele elemente, adică suma din stânga-sus.
        
            
442
                            </li>
        
            
443
                        </ol>
        
            
444
                        <p>
        
            
445
                            <code>
        
            
446
                                ps[i][j] =
        
            
447
                                <span class="sel4">a[i][j]</span>
        
            
448
                                + <span class="sel1">safe_get(ps, i - 1, j)</span>
        
            
449
                                + <span class="sel2">safe_get(ps, i, j - 1)</span>
        
            
450
                                - <span class="sel3">safe_get(ps, i - 1, j - 1)</span>;
        
            
451
                            </code>
        
            
452
                        </p>
        
            
453
                        <p>
        
            
454
                            Mai rămâne să calculăm suma pentru o anumită interogare.
        
            
455
                            De exemplu, de la <code>(1; 1)</code> până la
        
            
456
                            <code>(3; 2)</code>. Notăm <code>(i0; j0; i1; j1)</code>.
        
            
457
                        </p>
        
            
458
                        <table class="matrix" contenteditable="true">
        
            
459
                            <tr>
        
            
460
                                <td class="sel3">12</td>
        
            
461
                                <td class="sel1">12</td>
        
            
462
                                <td class="sel1">8</td>
        
            
463
                                <td>0</td>
        
            
464
                                <td>3</td>
        
            
465
                            </tr>
        
            
466
                            <tr>
        
            
467
                                <td class="sel2">11</td>
        
            
468
                                <td class="sel4">17</td>
        
            
469
                                <td class="sel4">20</td>
        
            
470
                                <td>20</td>
        
            
471
                                <td>27</td>
        
            
472
                            </tr>
        
            
473
                            <tr>
        
            
474
                                <td class="sel2">15</td>
        
            
475
                                <td class="sel4">18</td>
        
            
476
                                <td class="sel4">30</td>
        
            
477
                                <td>31</td>
        
            
478
                                <td>42</td>
        
            
479
                            </tr>
        
            
480
                            <tr>
        
            
481
                                <td class="sel2">26</td>
        
            
482
                                <td class="sel4">36</td>
        
            
483
                                <td class="sel4">57</td>
        
            
484
                                <td>66</td>
        
            
485
                                <td>89</td>
        
            
486
                            </tr>
        
            
487
                        </table>
        
            
488
                        <p>
        
            
489
                            Putem să o calculăm folosind doar sumele calculate deja.
        
            
490
                        </p>
        
            
491
                        <ol>
        
            
492
                            <li>
        
            
493
                                se ia valoarea ultimei celule din interval (în dreapta-jos);
        
            
494
                                aceea va reprezenta evident tot intervalul, dar și alte
        
            
495
                                elemente pe care le vom exclude;
        
            
496
                            </li>
        
            
497
                            <li>
        
            
498
                                se ia valoarea celulei de deasupra colțului dreapta-sus al
        
            
499
                                intervalului, care va conține doar elemente ce trebuie
        
            
500
                                excluse;
        
            
501
                            </li>
        
            
502
                            <li>
        
            
503
                                se ia valoarea celulei din stânga colțului stânga-jos al
        
            
504
                                intervalului, care va conține doar elemente ce trebuie
        
            
505
                                excluse;
        
            
506
                            </li>
        
            
507
                            <li>
        
            
508
                                și acum avem elemente excluse de două ori, și anume celula
        
            
509
                                aflată în stânga-sus față de colțul stânga-sus al
        
            
510
                                intervalului.
        
            
511
                            </li>
        
            
512
                        </ol>
        
            
513
            <pre><code><b>int</b> get_sum(vector&lt;vector&lt;<b>int</b>&gt;&gt; &amp;ps, <b>int const</b> i0, <b>int const</b> j0) {
        
            
514
                <b>return</b> <span class="sel4">safe_get(ps, i1, j1)</span>
        
            
515
                       - <span class="sel1">safe_get(ps, i1 - 1, j1)</span>
        
            
516
                       - <span class="sel2">safe_get(ps, i1, j1 - 1)</span>
        
            
517
                       + <span class="sel3">safe_get(ps, i1 - 1, j1 - 1)</span>;
        
            
518
            }</code></pre>
        
            
519
                    </section>
        
            
520
                    <section>
        
            
521
                        <h2>Alte sume parțiale (de discutat)</h2>
        
            
522
                        <ul>
        
            
523
                            <li>
        
            
524
                                Sume parțiale pentru indici cu rație (din x în x).
        
            
525
                            </li>
        
            
526
                            <li>
        
            
527
                                Sume parțiale pe diagonală.
        
            
528
                            </li>
        
            
529
                            <li>
        
            
530
                                Sume parțiale pe un trapez dreptunghic delimitat la
        
            
531
                                diagonală.
        
            
532
                            </li>
        
            
533
                            <li>
        
            
534
                                Sume parțiale pe triunghi dreptunghic.
        
            
535
                            </li>
        
            
536
                            <li>
        
            
537
                                Sume parțiale pe linii oblice care nu sunt neapărat
        
            
538
                                diagonale.
        
            
539
                            </li>
        
            
540
                            <li>
        
            
541
                                Sume parțiale pe paralelogram.
        
            
542
                            </li>
        
            
543
                        </ul>
        
            
544
                    </section>
        
            
545
                </body>
        
            
546
            </html>
        
            
547